Results 11 to 20 of about 1,033 (146)
Pathwidth of outerplanar graphs [PDF]
Journal of Graph Theory, 2006 AbstractWe are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin [3], after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a ...
Coudert, David +2 more
core +13 more sources
Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs [PDF]
Discrete Mathematics, 2002 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Mitsunori Togasaki, Koichi Yamazaki
openaire +2 more sources
Pathwidth of Circular-Arc Graphs [PDF]
, 2007 The pathwidth of a graph G is the minimum clique number of H minus one, over all interval supergraphs H of G. Although pathwidth is a well-known and well-studied graph parameter, there are extremely few graph classes for which pathwidh is known to be tractable in polynomial time.
Karol Suchan, Ioan Todinca
openaire +3 more sources
Approximating Pathwidth for Graphs of Small Treewidth [PDF]
ACM Transactions on Algorithms, 2021 We describe a polynomial-time algorithm which, given a graphGwith treewidtht, approximates the pathwidth ofGto within a ratio of\(O(t\sqrt {\log t})\). This is the first algorithm to achieve anf(t)-approximation for some functionf.Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a ...
Carla Groenland +3 more
openaire +15 more sources
Tree-decompositions of small pathwidth [PDF]
Electronic Notes in Discrete Mathematics, 2001 The treewidth \(\text{ tw}(G)\) of \(G\) can be defined as minimum width of a tree-decomposition of \(G\), or minimum \(\omega(H)-1\) of a chordal triangulation \(H\) of \(G\). Similarely, the pathwidth \(\text{ pw}(G)\) can be defined via path-decompositions or triangulations into interval graphs. Thereby a path-decomposition is a tree-decomposition \(
Telle, Jan Arne
openaire +4 more sources
Circumference and Pathwidth of Highly Connected Graphs [PDF]
Journal of Graph Theory, 2014 AbstractBirmele [J Graph Theory 2003] proved that every graph with circumference t has treewidth at most . Under the additional assumption of 2‐connectivity, such graphs have bounded pathwidth, which is a qualitatively stronger conclusion. Birmele's theorem was extended by Birmele et al.
Emily Abernethy Marshall, David R. Wood
openaire +4 more sources
CSP duality and trees of bounded pathwidth [PDF]
Theoretical Computer Science, 2010 We study non-uniform constraint satisfaction problems definable in monadic Datalog stratified by the use of non-linearity. We show how such problems can be described in terms of homomorphism dualities involving trees of bounded pathwidth and in algebraic terms. For this, we introduce a new parameter for trees that closely approximates pathwidth and can
Catarina Carvalho +2 more
openaire +3 more sources
New Algorithms for Mixed Dominating Set [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 A mixed dominating set is a collection of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for \textsc{Mixed Dominating Set}, resolving some open questions.
Louis Dublois +2 more
doaj +1 more source
Classes of graphs with restricted interval models [PDF]
Discrete Mathematics & Theoretical Computer Science, 1999 We introduce q-proper interval graphs as interval graphs with interval models in which no interval is properly contained in more than q other intervals, and also provide a forbidden induced subgraph characterization of this class of graphs. We initiate a
Andrzej Proskurowski, Jan Arne Telle
doaj +3 more sources
Recent Advances in Positive-Instance Driven Graph Searching
Algorithms, 2022 Research on the similarity of a graph to being a tree—called the treewidth of the graph—has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017).
Max Bannach, Sebastian Berndt
doaj +1 more source