Results 211 to 220 of about 13,814 (224)
Some of the next articles are maybe not open access.
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
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
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
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
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
2014
• O.k p log k/. • For all {v;w} 2 E, there is an i 2 I with v, w 2 Xi . • For all v 2 V , the set {i 2 I jv 2 Xi} induces a connected subtree of T . The width of a tree decomposition is max i2I jXi j 1, and the treewidth of a graph G is the minimum width of a tree decomposition of G (Fig. 1). An alternative definition is in terms of chordal graphs.
openaire +4 more sources
• O.k p log k/. • For all {v;w} 2 E, there is an i 2 I with v, w 2 Xi . • For all v 2 V , the set {i 2 I jv 2 Xi} induces a connected subtree of T . The width of a tree decomposition is max i2I jXi j 1, and the treewidth of a graph G is the minimum width of a tree decomposition of G (Fig. 1). An alternative definition is in terms of chordal graphs.
openaire +4 more sources
Treewidth of Circular-Arc Graphs
SIAM Journal on Discrete Mathematics, 1994It is shown that the treewidth of circular-arc graphs and the corresponding tree-decomposition can be found in \(O(n^ 3)\) time. Let \(G= (V,E)\) be a circular-arc graph corresponding to a family \(\{A_ 0, A_ 1,\dots, A_{n-1}\}\) of arcs on a unit circle. Define a left clique \(S_ i\) by \(S_ i= \{A_ j\mid A_ j\) contains the left end points of \(A_ i\}
C. Pandu Rangan +2 more
openaire +3 more sources