Results 11 to 20 of about 13,814 (224)
Separating layered treewidth and row treewidth [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 Layered treewidth and row treewidth are recently introduced graph parameters that have been key ingredients in the solution of several well-known open problems.
P. Bose +4 more
semanticscholar +4 more sources
Treewidth: Computational Experiments [PDF]
Electronic Notes in Discrete Mathematics, 2001 Many {\cal NP}-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for diverse
Arie M. C. A. Koster +2 more
openalex +12 more sources
Journal of Combinatorial Theory, Series B, 2005 Graphs of high girth have been much studied, especially in the context of the minimum vertex number of graphs of given girth and minimum degree. The authors study the treewidth \(\text{tw}(G)\) of a graph \(G\), giving a lower bound in terms of the girth \(g(G)\) and average degree \(d(G)\). They show that \[ \text{tw}(G)\geq c {1\over g(G)+1} (d(G)-1)^
L. Sunil Chandran, C. R. Subramanian
openalex +4 more sources
Journal of Combinatorial Theory, Series B, 2005 25 ...
L. Sunil Chandran, Naveen Sivadasan
openalex +5 more sources
Treewidth of Chordal Bipartite Graphs [PDF]
Journal of Algorithms, 1995 Summary: Chordal bipartite graphs are exactly those bipartite graphs in which every cycle of length at least six has a chord. The treewidth of a graph \(G\) is the smallest maximum cliquesize among all chordal supergraphs of \(G\) decreased by one.
Ton Kloks, Dieter Kratsch
openalex +8 more sources
ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2023 The core chase, a popular algorithm for answering conjunctive queries (CQs) over existential rules, is guaranteed to terminate and compute a finite universal model whenever one exists, leading to the equivalence of the universal-model-based and the chase-
Jean-François Baget +2 more
semanticscholar +1 more source
On treewidth approximations [PDF]
Electronic Notes in Discrete Mathematics, 2001 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Bouchitté, Vincent +3 more
openaire +5 more sources
Twin-width can be exponential in treewidth [PDF]
J. Comb. Theory B, 2022 For any small positive real $\varepsilon$ and integer $t>\frac{1}{\varepsilon}$, we build a graph with a vertex deletion set of size $t$ to a tree, and twin-width greater than $2^{(1-\varepsilon) t}$.
Édouard Bonnet, Hugues Déprés
semanticscholar +1 more source
Computing Treewidth on the GPU
arXiv, 2017 We present a parallel algorithm for computing the treewidth of a graph on a GPU. We implement this algorithm in OpenCL, and experimentally evaluate its performance. Our algorithm is based on an $O^*(2^{n})$-time algorithm that explores the elimination orderings of the graph using a Held-Karp like dynamic programming approach.
Tom C. van der Zanden +1 more
openalex +8 more sources
Treewidth, Circle Graphs, and Circular Drawings [PDF]
SIAM Journal on Discrete Mathematics, 2022 A circle graph is an intersection graph of a set of chords of a circle. We describe the unavoidable induced subgraphs of circle graphs with large treewidth. This includes examples that are far from the `usual suspects'.
Robert Hickingbotham +3 more
semanticscholar +1 more source