Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth

Summary, in English

We present a generic scheme for approximating NP-hard problems on graphs of treewidth k = omega (log n). When a tree-decomposition of width l is given, the scheme typically yields an l / log n-approximation factor; otherwise, an extra log k factor is incurred. Our method applies to several basic subgraph and partitioning problems, including the maximum independent set problem.

• Författare: A Czumaj; M M Halldorsson; Andrzej Lingas; J Nilsson
• Avdelning/ar: Computer Science
• Publiceringsår: 2005
• Språk: Engelska
• Sidor: 49-53
• Publikation/Tidskrift/Serie: Information Processing Letters
• Volym: 94
• Issue: 2
• Länkar: http://dx.doi.org/10.1016/j.ipl.2004.12.017
• Dokumenttyp: Artikel i tidskrift
• Förlag: Elsevier
• Ämne: Computer Science
• Nyckelord: bounded; NP-hard problems; partial k-trees; approximation algorithms; treewidth
• Status: Published
• Projekt: VR 2002-4049
• ISBN/ISSN/Övrigt: ISSN: 0020-0190