TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1993

COGA 5-Wheel

Page Content

to Navigation

Preprints 1993

The pathwidth and treewidth of cographs
Citation key Report-245-1990
Author Hans L. Bodlaender and Rolf H. Möhring
Title of Book Proc. 2nd Scand. Workshop on Algorithm Theory 1990, LNCS 447
Pages 301-309
Year 1990
Number 245
Note Journal Version in SIAM Journal on Discrete Mathematics 6 (1993), pp. 181-188
Publisher Springer-Verlag
Institution Technische Universität Berlin, Institut für Mathematik
Abstract We show that the pathwidth of a cograph equals its treewidth, and give a linear time algorithm to determine the pathwidth of a cograph and build a corresponding path-decomposition.
Bibtex Type of Publication Preprint
Download Bibtex entry

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe