Constant-degree graph expansions that preserve treewidth

DOI10.1007/s00453-009-9312-5zbMath1215.68186arXiv0707.3622OpenAlexW3106029909MaRDI QIDQ633842

Igor L. Markov, Yaoyun Shi

Publication date: 30 March 2011

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

algorithmstreewidthconstant degreegraph expansionsub-cubic graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (7)

Graphs of linear growth have bounded treewidth ⋮ Size-treewidth tradeoffs for circuits computing the element distinctness function ⋮ Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ Parameters Tied to Treewidth ⋮ EPG-representations with Small Grid-Size ⋮ Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs ⋮ Treewidth computations. II. Lower bounds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. III. Planar tree-width
• Network-based heuristics for constraint-satisfaction problems
• Graph minors. X: Obstructions to tree-decomposition
• Some APX-completeness results for cubic graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Bucket elimination: A unifying framework for reasoning
• NP-hard graph problems and boundary classes of graphs
• Treewidth: Characterizations, Applications, and Computations
• Simulating Quantum Computation by Contracting Tensor Networks
• Complexity of Finding Embeddings in a k-Tree

This page was built for publication: Constant-degree graph expansions that preserve treewidth