Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth

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

doi:10.1016/j.ipl.2004.12.017

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

Department of Computer Science

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	49-53
Number of pages	5
Journal	Information Processing Letters
Volume	94
Issue number	2
DOIs	https://doi.org/10.1016/j.ipl.2004.12.017
Publication status	Published - 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

Access to Document

10.1016/j.ipl.2004.12.017

Cite this

@article{97ff8ed9f32440309b781de4b864d4ae,

title = "Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth",

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.",

keywords = "Approximation algorithms, Bounded treewidth, NP-hard problems, Partial k-trees",

author = "Artur Czumaj and Halld{\'o}rsson, {Magn{\'u}s M.} and Andrzej Lingas and Johan Nilsson",

note = "Funding Information: * Corresponding author. E-mail addresses: czumaj@cis.njit.edu (A. Czumaj), mmh@hi.is (M.M. Halld{\'o}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.",

year = "2005",

month = apr,

day = "30",

doi = "10.1016/j.ipl.2004.12.017",

language = "English",

volume = "94",

pages = "49--53",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth

AU - Czumaj, Artur

AU - Halldórsson, Magnús M.

AU - Lingas, Andrzej

AU - Nilsson, Johan

N1 - 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.

PY - 2005/4/30

Y1 - 2005/4/30

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Bounded treewidth

KW - NP-hard problems

KW - Partial k-trees

UR - http://www.scopus.com/inward/record.url?scp=14644444118&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2004.12.017

DO - 10.1016/j.ipl.2004.12.017

M3 - Article

AN - SCOPUS:14644444118

VL - 94

SP - 49

EP - 53

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 2

ER -

Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth

Abstract

Bibliographical note

Other keywords

Access to Document

Fingerprint

Cite this