Results 231 to 240 of about 4,776 (247)
Some of the next articles are maybe not open access.
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
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
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
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
Treewidth Inapproximability and Tight ETH Lower Bound
Symposium on the Theory of ComputingDespite the (algorithmic) importance of treewidth, both its complexity and approximability present large knowledge gaps. While the best currently known polynomial-time approximation algorithm has ratio O(√logOPT), no approximation factor could be ruled ...
Édouard Bonnet
semanticscholar +1 more source
Chordal Graphs, Even‐Hole‐Free Graphs and Sparse Obstructions to Bounded Treewidth
Journal of Graph TheoryEven‐hole‐free graphs pose a central challenge in identifying hereditary classes of bounded treewidth. We investigate this matter by presenting and studying the following conjecture: for an integer and a graph , every even‐hole‐free graph of large enough
Sepehr Hajebi
semanticscholar +1 more source
Rapid Mixing for the Hardcore Glauber Dynamics and Other Markov Chains in Bounded-Treewidth Graphs
International Symposium on Algorithms and Computation, 2021We give a new rapid mixing result for a natural random walk on the independent sets of a graph $G$. We show that when $G$ has bounded treewidth, this random walk -- known as the Glauber dynamics for the hardcore model -- mixes rapidly for all fixed ...
D. Eppstein, Daniel Frishberg
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
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