A partial k-arboretum of graphs with bounded treewidth

H.L. Bodlaender

doi:10.1016/S0304-3975(97)00228-4

A partial k-arboretum of graphs with bounded treewidth

H.L. Bodlaender

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

681 Citations (Scopus)

Abstract

The notion of treewidth has seen to be a powerful vehicle for many graph algorithmic studies. This survey paper wants to give an overview of many classes of graphs that can be seen to have a uniform upper bound on the treewidth of graphs in the class. Also, some mutual relations between such classes are discussed.

Original language	English
Pages (from-to)	1-45
Number of pages	45
Journal	Theoretical Computer Science
Volume	209
Issue number	1–2
DOIs	https://doi.org/10.1016/S0304-3975(97)00228-4
Publication status	Published - 1998
Externally published	Yes

Keywords

Graph classes
Partial k-tree
Treewidth

Access to Document

10.1016/S0304-3975(97)00228-4

Cite this

@article{64da30a4a1de4f9fb1ae6cfe490d93e0,

title = "A partial k-arboretum of graphs with bounded treewidth",

abstract = "The notion of treewidth has seen to be a powerful vehicle for many graph algorithmic studies. This survey paper wants to give an overview of many classes of graphs that can be seen to have a uniform upper bound on the treewidth of graphs in the class. Also, some mutual relations between such classes are discussed.",

keywords = "Graph classes, Partial k-tree, Treewidth",

author = "H.L. Bodlaender",

year = "1998",

doi = "10.1016/S0304-3975(97)00228-4",

language = "English",

volume = "209",

pages = "1--45",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "1–2",

}

TY - JOUR

T1 - A partial k-arboretum of graphs with bounded treewidth

AU - Bodlaender, H.L.

PY - 1998

Y1 - 1998

N2 - The notion of treewidth has seen to be a powerful vehicle for many graph algorithmic studies. This survey paper wants to give an overview of many classes of graphs that can be seen to have a uniform upper bound on the treewidth of graphs in the class. Also, some mutual relations between such classes are discussed.

AB - The notion of treewidth has seen to be a powerful vehicle for many graph algorithmic studies. This survey paper wants to give an overview of many classes of graphs that can be seen to have a uniform upper bound on the treewidth of graphs in the class. Also, some mutual relations between such classes are discussed.

KW - Graph classes

KW - Partial k-tree

KW - Treewidth

U2 - 10.1016/S0304-3975(97)00228-4

DO - 10.1016/S0304-3975(97)00228-4

M3 - Article

VL - 209

SP - 1

EP - 45

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1–2

ER -

A partial k-arboretum of graphs with bounded treewidth

Abstract

Keywords

Access to Document

Fingerprint

Cite this