Results 81 to 90 of about 1,033 (146)

Crossing Number for Graphs with Bounded~Pathwidth [PDF]

, 2017
The crossing number is the smallest number of pairwise edge crossings when drawing a graph into the plane. There are only very few graph classes for which the exact crossing number is known or for which there at least exist constant approximation ratios.
Biedl, Therese, Mutzel, Petra, Chimani, Markus, Derka, Martin   +3 more
core   +1 more source

Kernel bounds for structural parameterizations of pathwidth

, 2012
Assuming the AND-distillation conjecture, the Pathwidth problem of determining whether a given graphG has pathwidth at most k admits no polynomial kernelization with respect to k. The present work studies the existence of polynomial kernels for Pathwidth
Jansen, BMP Bart, Hans L. Bodlaender, Stefan Kratsch, Bart M. P. Jansen, Kratsch, Stefan, Bodlaender, HL Hans   +5 more
core   +1 more source

Some Reduction Procedure for Computing Pathwidth of Undirected Graphs [PDF]

, 2015
Computing an invariant of a graph such as treewidth and pathwidth is one of the fundamental problems in graph algorithms. In general, determining the pathwidth of a graph is NP-hard.
IKEDA, Masataka, NAGAMOCHI, Hiroshi
core   +1 more source

Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming

Algorithms, 2018
Treedepth is a well-established width measure which has recently seen a resurgence of interest. Since graphs of bounded treedepth are more restricted than graphs of bounded tree- or pathwidth, we are interested in the algorithmic utility of this ...
Li-Hsuan Chen, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil   +3 more
doaj   +1 more source

The Treewidth and Pathwidth of Graph Unions

SIAM Journal on Discrete Mathematics
Given two $n$-vertex graphs $G_1$ and $G_2$ of bounded treewidth, is there an $n$-vertex graph $G$ of bounded treewidth having subgraphs isomorphic to $G_1$ and $G_2$? Our main result is a negative answer to this question, in a strong sense: we show that the answer is no even if $G_1$ is a binary tree and $G_2$ is a ternary tree.
Bogdan Alecu, Vadim V. Lozin, Daniel A. Quiroz, Roman Rabinovich 0001, Igor Razgon, Viktor Zamaraev   +5 more
openaire   +5 more sources

2-Layer Graph Drawings with Bounded Pathwidth [PDF]

, 2022
We determine which properties of 2-layer drawings characterise bipartite graphs of bounded ...
Wood, David R.
core  

On Exploring Temporal Graphs of Small Pathwidth

CoRR, 2018
We show that the Temporal Graph Exploration Problem is NP-complete, even when the underlying graph has pathwidth 2 and at each time step, the current graph is connected.
Bodlaender, Hans L., van der Zanden, Tom C.   +1 more
openaire   +6 more sources

Editorial. [PDF]

Theor Comput Sci, 2022
Calamoneri T.
europepmc   +1 more source

The structure of obstructions to treewidth and pathwidth

Electronic Notes in Discrete Mathematics, 1999
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire   +5 more sources

Abstract Bounded Persistence Pathwidth

, 2008
The role of graph width metrics, such as treewidth, pathwidth, and cliquewidth, is now seen as central in both algorithm design and the delineation of what is algorithmically possible.
Catherine Mccartin, Rodney G. Downey
core