Results 1 to 10 of about 2,730 (147)
From Pathwidth to Connected Pathwidth [PDF]
SIAM J. Discrete Mathematics 26 (2012) 1709-1732, 2010 It is proven that the connected pathwidth of any graph $G$ is at most $2\cdot\pw(G)+1$, where $\pw(G)$ is the pathwidth of $G$. The method is constructive, i.e. it yields an efficient algorithm that for a given path decomposition of width $k$ computes a connected path decomposition of width at most $2k+1$. The running time of the algorithm is $O(dk^2)$,
Dereniowski, Dariusz
arxiv +19 more sources
Kernel Bounds for Structural Parameterizations of Pathwidth [PDF]
Lecture Notes in Computer Science 7357 (2012) 352-363, 2012 Assuming the AND-distillation conjecture, the Pathwidth problem of determining whether a given graph G has pathwidth at most k admits no polynomial kernelization with respect to k. The present work studies the existence of polynomial kernels for Pathwidth with respect to other, structural, parameters. Our main result is that, unless NP is in coNP/poly,
B. Monien +14 more
arxiv +10 more sources
Bandwidth and pathwidth of three-dimensional grids [PDF]
arXiv, 2011 We study the bandwidth and the pathwidth of multi-dimensional grids. It can be shown for grids, that these two parameters are equal to a more basic graph parameter, the vertex boundary width. Using this fact, we determine the bandwidth and the pathwidth of three-dimensional grids, which were known only for the cubic case.
Yota Otachi, Ryohei Suda
arxiv +5 more sources
Circumference and Pathwidth of Highly Connected Graphs [PDF]
J. Graph Theory 79.3:222-232, 2015, 2013 Birmele [J. Graph Theory, 2003] proved that every graph with circumference t has treewidth at most t-1. Under the additional assumption of 2-connectivity, such graphs have bounded pathwidth, which is a qualitatively stronger result. Birmele's theorem was extended by Birmele, Bondy and Reed [Combinatorica, 2007] who showed that every graph without k ...
Marshall, Emily A., Wood, David R.
arxiv +7 more sources
$b$-Coloring Parameterized by Pathwidth is XNLP-complete [PDF]
arXiv, 2022 We show that the $b$-Coloring problem is complete for the class XNLP when parameterized by the pathwidth of the input graph. Besides determining the precise parameterized complexity of this problem, this implies that b-Coloring parameterized by pathwidth is $W[t]$-hard for all $t$, and resolves the parameterized complexity of $b$-Coloring parameterized
Lars Jaffke +2 more
arxiv +3 more sources
Triangulating planar graphs while keeping the pathwidth small [PDF]
arXiv, 2015 Any simple planar graph can be triangulated, i.e., we can add edges to it, without adding multi-edges, such that the result is planar and all faces are triangles. In this paper, we study the problem of triangulating a planar graph without increasing the pathwidth by much. We show that if a planar graph has pathwidth $k$, then we can triangulate it so
Thérèse Biedl
arxiv +3 more sources
TREEWIDTH and PATHWIDTH parameterized by vertex cover [PDF]
arXiv, 2013 After the number of vertices, Vertex Cover is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the Vertex Cover.
Chapelle, Mathieu +3 more
arxiv +5 more sources
Minor-closed graph classes with bounded layered pathwidth [PDF]
SIAM J. Discrete Math., 34(3), 1693-1709, 2020, 2018 We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if some apex-forest is not in the class. This generalises a theorem of Robertson and Seymour, which says that a minor-closed class of graphs has bounded pathwidth if and only if some forest is not in the class.
Vida Dujmović +4 more
arxiv +3 more sources
Linear Datalog and Bounded Path Duality of Relational Structures [PDF]
Logical Methods in Computer Science, 2005 In this paper we systematically investigate the connections between logics with a finite number of variables, structures of bounded pathwidth, and linear Datalog Programs.
Victor Dalmau
doaj +4 more sources
Matroid Pathwidth and Code Trellis Complexity [PDF]
arXiv, 2007 We relate the notion of matroid pathwidth to the minimum trellis state-complexity (which we term trellis-width) of a linear code, and to the pathwidth of a graph. By reducing from the problem of computing the pathwidth of a graph, we show that the problem of determining the pathwidth of a representable matroid is NP-hard.
Navin Kashyap
arxiv +3 more sources