Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems

DOI10.1007/978-3-642-32512-0_2zbMath1358.68111arXiv1109.4910OpenAlexW2143708942MaRDI QIDQ3167381

Yu Wu, Toniann Pitassi, Per Austrin

Publication date: 2 November 2012

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

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (6)

Approximation algorithms for digraph width parameters ⋮ Unnamed Item ⋮ A $c^k n$ 5-Approximation Algorithm for Treewidth ⋮ Lower bounds for treewidth of product graphs ⋮ Tight inapproximability of minimum maximal matching on bipartite graphs and related problems ⋮ The red-blue pebble game on trees and DAGs with large input

This page was built for publication: Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems