Technical Report 245-1990

Title

The pathwidth and treewidth of cographs

Authors

Hans L. Bodlaender and Rolf H. Möhring

Publication

Springer, Proc. 2nd Scand. Workshop on Algorithm Theory 1990, LNCS 447, 1990, pp. 301-309

Journal Version in SIAM Journal on Discrete Mathematics 6 (1993), pp. 181-188

Source

The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de

Classification

not available

Keywords

not available

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.