Results 61 to 70 of about 2,587 (156)
Minor-Closed Graph Classes with Bounded Layered Pathwidth [PDF]
SIAM Journal on Discrete Mathematics, 2020 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
openaire +3 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 +1 more source
On the Geometric Ramsey Number of Outerplanar Graphs
, 2013 We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases. We also prove that the geometric Ramsey numbers of the ladder graph on $2n$ vertices are bounded by $O(n^{3})$ and $O(
Cibulka, Josef +4 more
core +1 more source
Strong-mixed searching and pathwidth [PDF]
Journal of Combinatorial Optimization, 2006 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +1 more source
LTL Fragments are Hard for Standard Parameterisations
, 2015 We classify the complexity of the LTL satisfiability and model checking problems for several standard parameterisations. The investigated parameters are temporal depth, number of propositional variables and formula treewidth, resp., pathwidth.
Lück, Martin, Meier, Arne
core +1 more source
Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class [PDF]
, 2018 We develop a framework for generalizing approximation algorithms from the structural graph algorithm literature so that they apply to graphs somewhat close to that class (a scenario we expect is common when working with real-world networks) while still ...
Demaine, Erik D. +7 more
core +2 more sources
The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
AlgorithmsTree-width and path-width are well-known graph parameters. Many NP-hard graph problems admit polynomial-time solutions when restricted to graphs of bounded tree-width or bounded path-width. In this work, we study the behavior of tree-width and path-width
Frank Gurski, Robin Weishaupt
doaj +1 more source
Hitting minors, subdivisions, and immersions in tournaments
, 2018 The Erd\H{o}s-P\'osa property relates parameters of covering and packing of combinatorial structures and has been mostly studied in the setting of undirected graphs.
Raymond, Jean-Florent
core +1 more source
Forbidden Directed Minors and Kelly-width [PDF]
, 2014 Partial 1-trees are undirected graphs of treewidth at most one. Similarly, partial 1-DAGs are directed graphs of KellyWidth at most two. It is well-known that an undirected graph is a partial 1-tree if and only if it has no K_3 minor.
Kintali, Shiva, Zhang, Qiuyi
core
$n$-permutability and linear Datalog implies symmetric Datalog
, 2018 We show that if $\mathbb A$ is a core relational structure such that CSP($\mathbb A$) can be solved by a linear Datalog program, and $\mathbb A$ is $n$-permutable for some $n$, then CSP($\mathbb A$) can be solved by a symmetric Datalog program (and thus ...
Kazda, Alexandr
core +1 more source