Results 11 to 20 of about 5,860 (222)
Induced subgraphs and tree decompositions V. One neighbor in a hole [PDF]
Journal of Graph Theory 105 (2023), 542-561, 2022 What are the unavoidable induced subgraphs of graphs with large treewidth? It is well-known that the answer must include a complete graph, a complete bipartite graph, all subdivisions of a wall and line graphs of all subdivisions of a wall (we refer to these graphs as the "basic treewidth obstructions"). So it is natural to ask whether graphs excluding
Tara Abrishami +5 more
arxiv +2 more sources
An Experimental Study of the Treewidth of Real-World Graph Data (Extended Version) [PDF]
arXiv, 2019 Treewidth is a parameter that measures how tree-like a relational instance is, and whether it can reasonably be decomposed into a tree. Many computation tasks are known to be tractable on databases of small treewidth, but computing the treewidth of a given instance is intractable.
Silviu Maniu, P. Senellart, Suraj Jog
arxiv +3 more sources
Taming High Treewidth with Abstraction, Nested Dynamic Programming, and Database Technology [PDF]
Theory and Applications of Satisfiability Testing – SAT 202023rd International Conference, 2020 Treewidth is one of the most prominent structural parameters. While numerous theoretical results establish tractability under the assumption of fixed treewidth, the practical success of exploiting this parameter is far behind what theoretical runtime ...
Hecher M, Thier P, Woltran S.
europepmc +2 more sources
Benchmarking treewidth as a practical component of tensor network simulations. [PDF]
PLoS ONE, 2018 Tensor networks are powerful factorization techniques which reduce resource requirements for numerically simulating principal quantum many-body systems and algorithms.
Eugene F Dumitrescu +5 more
doaj +2 more sources
A Faster Small Treewidth SDP Solver [PDF]
arXiv.org, 2022 Semidefinite programming is a fundamental tool in optimization and theoretical computer science. It has been extensively used as a black-box for solving many problems, such as embedding, complexity, learning, and discrepancy.
Yuzhou Gu, Zhao Song
semanticscholar +1 more source
Metric dimension parameterized by treewidth in chordal graphs [PDF]
International Workshop on Graph-Theoretic Concepts in Computer Science, 2023 The metric dimension has been introduced independently by Harary, Melter and Slater in 1975 to identify vertices of a graph G using its distances to a subset of vertices of G.
N. Bousquet +2 more
semanticscholar +1 more source
The treewidth of 2-section of hypergraphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 Let $H=(V,F)$ be a simple hypergraph without loops. $H$ is called linear if $|f\cap g|\le 1$ for any $f,g\in F$ with $f\not=g$. The $2$-section of $H$, denoted by $[H]_2$, is a graph with $V([H]_2)=V$ and for any $ u,v\in V([H]_2)$, $uv\in E([H]_2)$ if ...
Ke Liu, Mei Lu
doaj +1 more source
A Single-Exponential Time 2-Approximation Algorithm for Treewidth [PDF]
IEEE Annual Symposium on Foundations of Computer Science, 2021 We give an algorithm, that given an n-vertex graph $G$ and an integer k, in time 2O(k)n either outputs a tree decomposition of $G$ of width at most 2k + 1 or determines that the treewidth of $G$ is larger than k.
T. Korhonen
semanticscholar +1 more source
Improved product structure for graphs on surfaces [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 Dujmovi\'c, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that for every graph $G$ with Euler genus $g$ there is a graph $H$ with treewidth at most 4 and a path $P$ such that $G\subseteq H \boxtimes P \boxtimes K_{\max\{2g,3\}}$. We improve
Marc Distel +3 more
doaj +1 more source
Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure [PDF]
J. Comb. Theory B, 2022 We continue the study of $(\mathrm{tw},\omega)$-bounded graph classes, that is, hereditary graph classes in which the treewidth can only be large due to the presence of a large clique, with the goal of understanding the extent to which this property has ...
Clément Dallard +2 more
semanticscholar +1 more source