The algorithmic theory of treewidth

Hans L. Bodlaender

doi:10.1016/S1571-0653(05)80116-7

The algorithmic theory of treewidth

Hans L. Bodlaender^*

^*Corresponding author for this work

External unknown

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

Treewidth is a graph measure with several applications. In this abstract, it is discussed that many otherwise intractable problems become polynomial or linear time solvable when restricted to graphs of bounded treewidth, and some other algorithmic results that use treewidth (e.g., applied to planar graphs) are discussed.

Original language	English
Pages (from-to)	27-30
Number of pages	4
Journal	Electronic Notes in Discrete Mathematics
Volume	5
DOIs	https://doi.org/10.1016/S1571-0653(05)80116-7
Publication status	Published - 1 Jul 2000
Externally published	Yes

Keywords

graph algorithms
partial k-tree
treewidth

Access to Document

10.1016/S1571-0653(05)80116-7

Cite this

@article{ed78eeaec0d349ec9f636795dd6a9f8c,

title = "The algorithmic theory of treewidth",

abstract = "Treewidth is a graph measure with several applications. In this abstract, it is discussed that many otherwise intractable problems become polynomial or linear time solvable when restricted to graphs of bounded treewidth, and some other algorithmic results that use treewidth (e.g., applied to planar graphs) are discussed.",

keywords = "graph algorithms, partial k-tree, treewidth",

author = "Bodlaender, {Hans L.}",

year = "2000",

month = jul,

day = "1",

doi = "10.1016/S1571-0653(05)80116-7",

language = "English",

volume = "5",

pages = "27--30",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - The algorithmic theory of treewidth

AU - Bodlaender, Hans L.

PY - 2000/7/1

Y1 - 2000/7/1

N2 - Treewidth is a graph measure with several applications. In this abstract, it is discussed that many otherwise intractable problems become polynomial or linear time solvable when restricted to graphs of bounded treewidth, and some other algorithmic results that use treewidth (e.g., applied to planar graphs) are discussed.

AB - Treewidth is a graph measure with several applications. In this abstract, it is discussed that many otherwise intractable problems become polynomial or linear time solvable when restricted to graphs of bounded treewidth, and some other algorithmic results that use treewidth (e.g., applied to planar graphs) are discussed.

KW - graph algorithms

KW - partial k-tree

KW - treewidth

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

U2 - 10.1016/S1571-0653(05)80116-7

DO - 10.1016/S1571-0653(05)80116-7

M3 - Article

AN - SCOPUS:34247395841

SN - 1571-0653

VL - 5

SP - 27

EP - 30

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

The algorithmic theory of treewidth

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this