Results 1 to 10 of about 1,033 (146)
Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth [PDF]
Journal of Experimental Algorithmics, 2016 Path decompositions of graphs are an important ingredient of dynamic programming algorithms for solving efficiently many NP-hard problems. Therefore, computing the pathwidth and associated path decomposition of graphs has both a theoretical and practical interest.
David Coudert +2 more
exaly +5 more sources
Outerplanar Obstructions for Matroid Pathwidth
Electronic Notes in Discrete Mathematics, 2011 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Koichi Yamazaki, Dimitrios M. Thilikos
exaly +9 more sources
From Pathwidth to Connected Pathwidth [PDF]
SIAM Journal on Discrete Mathematics, 2012 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)$,
Dariusz Dereniowski
exaly +7 more sources
Cycle decompositions of pathwidth‐6 graphs [PDF]
Journal of Graph Theory, Volume 94, Issue 2, Page 224-251, June 2020., 2020 Abstract Hajós' conjecture asserts that a simple Eulerian graph on n vertices can be decomposed into at most ⌊ ( n − 1 ) / 2 ⌋ cycles. The conjecture is only proved for graph classes in which every element contains vertices of degree 2 or 4. We develop new techniques to construct cycle decompositions.
Elke Fuchs +2 more
wiley +6 more sources
On the Pathwidth of Hyperbolic 3-Manifolds
Computing in Geometry and Topology, 2022 According to Mostow's celebrated rigidity theorem, the geometry of closed hyperbolic 3-manifolds is already determined by their topology. In particular, the volume of such manifolds is a topological invariant and, as such, has been subject of ...
Kristóf Huszár
doaj +6 more sources
Tournament pathwidth and topological containment
Journal of Combinatorial Theory Series B, 2013 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Paul Seymour
exaly +4 more sources
Separating layered treewidth and row treewidth [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 Layered treewidth and row treewidth are recently introduced graph parameters that have been key ingredients in the solution of several well-known open problems.
Prosenjit Bose +4 more
doaj +1 more source
The pathwidth and treewidth of cographs [PDF]
SIAM Journal on Discrete Mathematics, 1990 Summary: It is shown that the pathwidth of a cograph equals its treewidth, and a linear time algorithm to determine the pathwidth of a cograph and build a corresponding path-decomposition is given.
Hans L. Bodlaender, Rolf H. Möhring
openaire +5 more sources
A new two-variable generalization of the chromatic polynomial [PDF]
Discrete Mathematics & Theoretical Computer Science, 2003 We present a two-variable polynomial, which simultaneously generalizes the chromatic polynomial, the independence polynomial, and the matching polynomial of a graph.
Klaus Dohmen +2 more
doaj +3 more sources
Two Results on Layered Pathwidth and Linear Layouts
Journal of Graph Algorithms and Applications, 2021 Layered pathwidth is a new graph parameter studied by Bannister et al. (2015). In this paper we present two new results relating layered pathwidth to two types of linear layouts. Our first result shows that, for any graph $G$, the stack number of $G$ is
Vida Dujmović, Pat Morin, Céline Yelle
doaj +1 more source