Results 211 to 220 of about 5,860 (222)
On treewidth and related parameters of random geometric graphs *
, 2017 Dieter Mitsche, Guillem Perarnau
openalex +1 more source
Some of the next articles are maybe not open access.
Related searches:
Related searches:
IEEE Annual Symposium on Foundations of Computer Science, 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 +1 more source
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 +1 more source
Treewidth Is NP-Complete on Cubic Graphs
International Symposium on Parameterized and Exact Computation, 2023In 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
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=
Tesshu Hanaka, M. Lampis
semanticscholar +1 more source
Faster Sampling Algorithms for Polytopes with Small Treewidth
BigData Congress [Services Society]Sampling is a fundamental problem in optimization, machine learning and theoretical computer science. A common region of interest for sampling is the polytope, which is defined by a set of linear inequalities.
Yekun Ke +3 more
semanticscholar +1 more source
Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs
Embedded Systems and Applications, 2021We give polynomial-time approximation schemes for monotone maximization problems expressible in terms of distances (up to a fixed upper bound) and efficiently solvable in graphs of bounded treewidth.
Zdenek Dvorák, A. Lahiri
semanticscholar +1 more source
Hardness of Metric Dimension in Graphs of Constant Treewidth
Algorithmica, 2021The Metric Dimension problem asks for a minimum-sized resolving set in a given (unweighted, undirected) graph G. Here, a set S⊆V(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb ...
Shaohua Li, Marcin Pilipczuk
semanticscholar +1 more source
Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal
International Colloquium on Automata, Languages and Programming, 2021The Subgraph Isomorphism problem is of considerable importance in computer science. We examine the problem when the pattern graph H is of bounded treewidth, as occurs in a variety of applications.
K. Bringmann, Jasper Slusallek
semanticscholar +1 more source
Minimum Stable Cut and Treewidth
International Colloquium on Automata, Languages and Programming, 2021A stable or locally-optimal cut of a graph is a cut whose weight cannot be increased by changing the side of a single vertex. In this paper we study Minimum Stable Cut, the problem of finding a stable cut of minimum weight. Since this problem is NP-hard,
M. Lampis
semanticscholar +1 more source