Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
(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:
https://lup.lub.lu.se/record/247096
- author
- Czumaj, A ; Halldorsson, M M ; Lingas, Andrzej LU and Nilsson, J
- organization
- publishing date
- 2005
- 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}}, }