Results 241 to 250 of about 14,736 (264)
2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023 We present a data structure that for a dynamic graph G that is updated by edge insertions and deletions, maintains a tree decomposition of G of width at most $6 k+5$ under the promise that the treewidth of G never grows above k. The amortized update time
T. Korhonen +4 more
semanticscholar +3 more sources
Some of the next articles are maybe not open access.
Related searches:
Related searches:
Journal of Algorithms, 1997
Summary: We consider a special variant of tree-decompositions, called domino tree-decompositions, and the related notion of domino treewidth. In a domino tree- decomposition, each vertex of the graph belongs to at most two nodes of the tree. We prove that for every \(k\), \(d\), there exists a constant \(c_{k,d}\) such that a graph with treewidth at ...
Bodlaender, Hans, Engelfriet, Joost
openaire +3 more sources
Summary: We consider a special variant of tree-decompositions, called domino tree-decompositions, and the related notion of domino treewidth. In a domino tree- decomposition, each vertex of the graph belongs to at most two nodes of the tree. We prove that for every \(k\), \(d\), there exists a constant \(c_{k,d}\) such that a graph with treewidth at ...
Bodlaender, Hans, Engelfriet, Joost
openaire +3 more sources
Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
International Workshop on Graph-Theoretic Concepts in Computer Science, 2022Twin-width is a newly introduced graph width parameter that aims at generalizing a wide range of"nicely structured"graph classes. In this work, we focus on obtaining good bounds on twin-width $\text{tww}(G)$ for graphs $G$ from a number of classic graph ...
Hugo Jacob, Marcin Pilipczuk
semanticscholar +1 more source
Hedonic Games and Treewidth Revisited
Embedded Systems and Applications, 2022We revisit the complexity of the well-studied notion of Additively Separable Hedonic Games (ASHGs). Such games model a basic clustering or coalition formation scenario in which selfish agents are represented by the vertices of an edge-weighted digraph $G=
T. Hanaka, M. Lampis
semanticscholar +1 more source
Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts
International Workshop on Graph-Theoretic Concepts in Computer Science, 2022Decompositional parameters such as treewidth are commonly used to obtain fixed-parameter algorithms for NP-hard graph problems. For problems that are W[1]-hard parameterized by treewidth, a natural alternative would be to use a suitable analogue of ...
Cornelius Brand +4 more
semanticscholar +1 more source
Treewidth Is NP-Complete on Cubic Graphs
International Symposium on Parameterized and Exact ComputationIn this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9.
H. Bodlaender +8 more
semanticscholar +1 more source
Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
arXiv.orgMany recent works address the question of characterizing induced obstructions to bounded treewidth. In 2022, Lozin and Razgon completely answered this question for graph classes defined by finitely many forbidden induced subgraphs.
Clément Dallard +6 more
semanticscholar +1 more source
Every Graph is Essential to Large Treewidth
arXiv.orgWe show that for every graph $H$, there is a hereditary weakly sparse graph class $\mathcal C_H$ of unbounded treewidth such that the $H$-free (i.e., excluding $H$ as an induced subgraph) graphs of $\mathcal C_H$ have bounded treewidth.
Bogdan Alecu +3 more
semanticscholar +1 more source
On treewidth and maximum cliques
Innovations in Graph TheoryWe construct classes of graphs that are variants of the so-called layered wheel. One of their key properties is that while the treewidth is bounded by a function of the clique number, the construction can be adjusted to make the dependence grow ...
Maria Chudnovsky, Nicolas Trotignon
semanticscholar +1 more source