An Efficient Partitioning Oracle for Bounded-Treewidth Graphs

DOI10.1007/978-3-642-22935-0_45zbMath1343.68294arXiv1106.4587OpenAlexW2132071831MaRDI QIDQ3088124

Avinatan Hassidim, Huy N. Nguyen, Krzysztof Onak, Alan Edelman

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1106.4587

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs, Testing outerplanarity of bounded degree graphs, Unnamed Item, Vertex-Coloring with Star-Defects, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. III. Planar tree-width
• On the hardness of approximating minimum vertex cover
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• On tree-partition-width
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On digraph coloring problems and treewidth duality
• Recognizing Berge graphs
• Parameter testing in bounded degree graphs of subexponential growth
• Testing Outerplanarity of Bounded Degree Graphs
• Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
• Graph minors. II. Algorithmic aspects of tree-width
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Some results on tree decomposition of graphs
• Approximating the distance to properties in bounded-degree and general sparse graphs
• Local Graph Partitions for Approximation and Testing
• An improved constant-time approximation algorithm for maximum~matchings
• Every property of hyperfinite graphs is testable
• Property testing in bounded degree graphs