Advanced

Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth

Czumaj, A; Halldorsson, M M; Lingas, Andrzej LU and Nilsson, J (2005) In Information Processing Letters 94(2). p.49-53
Abstract
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.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
bounded, NP-hard problems, partial k-trees, approximation algorithms, treewidth
in
Information Processing Letters
volume
94
issue
2
pages
49 - 53
publisher
Elsevier
external identifiers
  • wos:000228035800001
  • scopus:14644444118
ISSN
0020-0190
DOI
10.1016/j.ipl.2004.12.017
project
VR 2002-4049
language
English
LU publication?
yes
id
3a479c4c-576b-402e-bf9c-71652f927855 (old id 247096)
date added to LUP
2007-08-02 14:16:21
date last changed
2017-04-09 04:21:26
@article{3a479c4c-576b-402e-bf9c-71652f927855,
  abstract     = {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.},
  author       = {Czumaj, A and Halldorsson, M M and Lingas, Andrzej and Nilsson, J},
  issn         = {0020-0190},
  keyword      = {bounded,NP-hard problems,partial k-trees,approximation algorithms,treewidth},
  language     = {eng},
  number       = {2},
  pages        = {49--53},
  publisher    = {Elsevier},
  series       = {Information Processing Letters},
  title        = {Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth},
  url          = {http://dx.doi.org/10.1016/j.ipl.2004.12.017},
  volume       = {94},
  year         = {2005},
}