Results 21 to 30 of about 3,161 (171)
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
Minor-closed graph classes with bounded layered pathwidth [PDF]
SIAM Journal on Discrete Mathematics, 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 ...
V. Dujmović +4 more
semanticscholar +3 more sources
Counting independent sets in graphs with bounded bipartite pathwidth [PDF]
International Workshop on Graph-Theoretic Concepts in Computer Science, 2018 We show that a simple Markov chain, the Glauber dynamics, can efficiently sample independent sets almost uniformly at random in polynomial time for graphs in a certain class.
M. Dyer +2 more
semanticscholar +3 more sources
Clustered colouring of graph classes with bounded treedepth or pathwidth [PDF]
Combinatorics, probability & computing, 2020 The "clustered chromatic number" of a class of graphs is the minimum integer $k$ such that for some integer $c$ every graph in the class is $k$-colourable with monochromatic components of size at most $c$.
S. Norin, A. Scott, D. Wood
semanticscholar +3 more sources
Crossing Number for Graphs with Bounded Pathwidth [PDF]
Algorithmica, 2020 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 +3 more
openaire +7 more sources
Majority constraints have bounded pathwidth duality [PDF]
European Journal of Combinatorics, 2008 This work was partially supported by the UK EPSRC grant EP/C54384X/1. Part of this work was done when both authors visited the Isaac Newton Institute for Mathematical Sciences, Cambridge. The financial support provided by the Institute is gratefully acknowledged.
Dalmau, V., Krokhin, A.
openaire +4 more sources
The structure of obstructions to treewidth and pathwidth
Electronic Notes in Discrete Mathematics, 1999 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Janka Chlebı́ková
openaire +6 more sources
Strong-mixed searching and pathwidth [PDF]
Journal of Combinatorial Optimization, 2006 In this paper, we propose a new search model, called strong-mixed search, which is a generalization of the mixed search. We show that the strong-mixed search number of a graph equals the pathwidth of the graph. We also describe relationships between the strong-mixed search number and other search numbers.
Boting Yang
openaire +3 more sources
Tree-decompositions of small pathwidth
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 \(
Jan Arne Telle
openaire +5 more sources
CSP duality and trees of bounded pathwidth
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
Carvalho, Catarina +2 more
openaire +4 more sources