Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
; ; and
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
2016-04-01 16:34:37
date last changed
2022-01-28 20:39:28
@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}},
  keywords     = {{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}},
  doi          = {{10.1016/j.ipl.2004.12.017}},
  volume       = {{94}},
  year         = {{2005}},
}