The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth

På svenska

Author

Summary, in English

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.

Department/s

  • Computer Science

Publishing year

2005

Language

English

Pages

49-53

Publication/Series

Information Processing Letters

Volume

94

Issue

2

Document type

Journal article

Publisher

Elsevier

Topic

  • Computer Science

Keywords

  • bounded
  • NP-hard problems
  • partial k-trees
  • approximation algorithms
  • treewidth

Status

Published

Project

  • VR 2002-4049

ISBN/ISSN/Other

  • ISSN: 0020-0190