Results 1 to 10 of about 3,176 (170)
Pathwidth Versus Cocircumference [PDF]
SIAM Journal on Discrete Mathematics, 2023 The {\em circumference} of a graph $G$ with at least one cycle is the length of a longest cycle in $G$. A classic result of Birmel\'e (2003) states that the treewidth of $G$ is at most its circumference minus $1$. In case $G$ is $2$-connected, this upper
Marcin Brianski, G. Joret, M. Seweryn
semanticscholar +3 more sources
From Pathwidth to Connected Pathwidth [PDF]
SIAM Journal on Discrete Mathematics, 2011 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.
Dereniowski, Dariusz
core +10 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 +5 more sources
On Approximating Cutwidth and Pathwidth [PDF]
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), 2023 We study graph ordering problems with a min-max objective. A classical problem of this type is cutwidth, where given a graph we want to order its vertices such that the number of edges crossing any point is minimized.
Nikhil Bansal +2 more
semanticscholar +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
Circumference and Pathwidth of Highly Connected Graphs [PDF]
Journal of Graph Theory, 2014 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
Marshall, Emily A., Wood, David R.
core +4 more sources
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, Nicolas Nisse
exaly +3 more sources
The treewidth and pathwidth of graph unions [PDF]
SIAM Journal on Discrete Mathematics, 2022 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
Bogdan Alecu +5 more
semanticscholar +4 more sources
Approximating Pathwidth for Graphs of Small Treewidth [PDF]
ACM Transactions on Algorithms, 2020 We describe a polynomial-time algorithm which, given a graph G with treewidth t, approximates the pathwidth of G to within a ratio of \(O(t\sqrt {\log t})\) . This is the first algorithm to achieve an f(t)-approximation for some function f.
Carla Groenland +3 more
semanticscholar +10 more sources
arXiv.orgMotivated by the importance of dynamic programming (DP) in parameterized complexity, we consider several fine-grained questions, such as the following examples: (i) can Dominating Set be solved in time $(3-\epsilon)^{pw}n^{O(1)}$?
M. Lampis
semanticscholar +4 more sources