THE PATHWIDTH AND TREEWIDTH OF COGRAPHS

Authors
BODLAENDER HL MOHRING RH
Citation
Hl. Bodlaender et Rh. Mohring, THE PATHWIDTH AND TREEWIDTH OF COGRAPHS, SIAM journal on discrete mathematics, 6(2), 1993, pp. 181-188
Citations number
23
Categorie Soggetti
Mathematics,Mathematics
Journal title
SIAM journal on discrete mathematics → ACNP
ISSN journal
08954801
Volume
6
Issue
2
Year of publication
1993
Pages
181 - 188
Database
ISI
SICI code
0895-4801(1993)6:2<181:TPATOC>2.0.ZU;2-T
Abstract
It is shown that the pathwidth of a cograph equals its treewidth, and a linear time algorithm to determine the pathwidth of a cograph and bu ild a corresponding path-decomposition is given.