Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth

DOI10.1016/j.ipl.2004.12.017zbMath1182.68361OpenAlexW1965171369MaRDI QIDQ1041722

Andrzej Lingas, Johan Nilsson, Magnús M. Halldórsson, Artur Czumaj

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.12.017

zbMATH Keywords

approximation algorithmsNP-hard problemsbounded treewidthpartial \(k\)-trees

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items

On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ New tools and connections for exponential-time approximation

Cites Work

• Unnamed Item
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Treewidth. Computations and approximations
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Approximating Maximum Clique by Removing Subgraphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth