Results 61 to 70 of about 2,549 (154)
The treewidth and pathwidth of hypercubes
Discrete Mathematics, 2006 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Sunil Chandran, L., Kavitha, T.
openaire +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
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
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
Tournament pathwidth and topological containment
Journal of Combinatorial Theory, Series B, 2013 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Fradkin, Alexandra, Seymour, Paul
openaire +2 more sources
Parameterized Complexity of Vertex Splitting to Pathwidth at most 1 [PDF]
, 2023 Jakob Baumann +2 more
openalex +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
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