Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

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

Original languageEnglish
Pages (from-to)49-53
Number of pages5
JournalInformation Processing Letters
Volume94
Issue number2
DOIs
Publication statusPublished - 30 Apr 2005

Bibliographical note

Funding Information:
* Corresponding author. E-mail addresses: czumaj@cis.njit.edu (A. Czumaj), mmh@hi.is (M.M. Halldórsson), andrzej.lingas@cs.lth.se (A. Lingas), johann@brics.dk (J. Nilsson). 1 Research supported in part by NSF grants CCR-0105701 and CCR-0313219. 2 BRICS (Basic Research in Computer Science) is funded by the Danish National Research Foundation.

Other keywords

  • Approximation algorithms
  • Bounded treewidth
  • NP-hard problems
  • Partial k-trees

Fingerprint

Dive into the research topics of 'Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth'. Together they form a unique fingerprint.

Cite this