Algorithmic aspects of tree width (Q4407447)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1944139
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Algorithmic aspects of tree width |
scientific article; zbMATH DE number 1944139 |
Statements
2003
0 references
treewidth
0 references
graph algorithms
0 references
dynamic programming
0 references
partial \(k\)-trees
0 references
0.9571321
0 references
0 references
0 references
0.9371372
0 references
0.9371372
0 references
0.93704194
0 references
0 references
0 references
0.92467725
0 references
0 references
Algorithmic aspects of tree width (English)
0 references
The paper gives a survey on recent results on graph algorithms that use the notions of treewidth and tree decomposition. Examples of problems where dynamic programming and divide and conquer strategies are used to solve graph problems are given, and the notions of treewidth and tree decomposition are introduced, and equivalence with other definitions is shown. The paper discusses how to find tree decompositions of bounded width, and how to use them, with applications. Also, a forbidden subgraph characterization of graphs of bounded treewidth is shown. For the entire collection see [Zbl 1005.00014].
0 references
