Results 21 to 30 of about 13,679 (262)
Treewidth of Chordal Bipartite Graphs [PDF]
Journal of Algorithms, 1995 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. We present a polynomial time algorithm for the exact computation of the treewidth of all chordal bipartite graphs.
Ton Kloks, Dieter Kratsch
openalex +7 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
Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth [PDF]
International Workshop on Graph-Theoretic Concepts in Computer Science, 2023 We study connectivity problems from a fine-grained parameterized perspective. Cygan et al. (TALG 2022) obtained algorithms with single-exponential running time $\alpha^{tw} n^{O(1)}$ for connectivity problems parameterized by treewidth ($tw$) by ...
Falko Hegerfeld, Stefan Kratsch
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
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
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
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
Product structure of graph classes with bounded treewidth [PDF]
Combinatorics, probability & computing, 2022 We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph.
Rutger Campbell +10 more
semanticscholar +1 more source
Low Treewidth Embeddings of Planar and Minor-Free Metrics [PDF]
IEEE Annual Symposium on Foundations of Computer Science, 2022 Cohen-Addad, Filtser, Klein and Le [FOCS’20] constructed a stochastic embedding of minor-free graphs of diameter D into graphs of treewidth $O_{\epsilon}(\log n)$ with expected additive distortion $+\epsilon D$. Cohen-Addad et al. then used the embedding
Arnold Filtser, Hung Le
semanticscholar +1 more source
Constant Congestion Brambles [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 A bramble in an undirected graph $G$ is a family of connected subgraphs of $G$ such that for every two subgraphs $H_1$ and $H_2$ in the bramble either $V(H_1) \cap V(H_2) \neq \emptyset$ or there is an edge of $G$ with one endpoint in $V(H_1)$ and the ...
Meike Hatzel +3 more
doaj +1 more source