Inapproximability of Treewidth and Related Problems
From MaRDI portal
Publication:5408191
DOI10.1613/jair.4030zbMath1361.68173OpenAlexW256842657WikidataQ57568022 ScholiaQ57568022MaRDI QIDQ5408191
Yu Wu, Toniann Pitassi, Per Austrin, David Liu
Publication date: 9 April 2014
Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1613/jair.4030
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (11)
On the effectiveness of the incremental approach to minimal chordal edge modification ⋮ Computing Tree Decompositions ⋮ Scheduling series-parallel task graphs to minimize peak memory ⋮ Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ On the tractability of \(( k , i )\)-coloring ⋮ On the complexity of computing treebreadth ⋮ Algorithms for automatic ranking of participants and tasks in an anonymized contest ⋮ Unnamed Item ⋮ Minimum fill-in: inapproximability and almost tight lower bounds ⋮ On the Complexity of Computing Treebreadth ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
This page was built for publication: Inapproximability of Treewidth and Related Problems
