The Pathwidth and Treewidth of Cographs

Hans Bodlaender; Rolf H. Möhring

The Pathwidth and Treewidth of Cographs

Decision Support Systems

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

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 build a corresponding path-decomposition is given.

Original language	English
Pages (from-to)	181-188
Journal	SIAM Journal on Discrete Mathematics
Volume	6
Issue number	2
Publication status	Published - 1993

Cite this

@article{3d7f83cb674e45aa977593dfea065cea,

title = "The Pathwidth and Treewidth of Cographs",

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 build a corresponding path-decomposition is given.",

author = "Hans Bodlaender and M{\"o}hring, {Rolf H.}",

year = "1993",

language = "English",

volume = "6",

pages = "181--188",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - The Pathwidth and Treewidth of Cographs

AU - Bodlaender, Hans

AU - Möhring, Rolf H.

PY - 1993

Y1 - 1993

N2 - 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 build a corresponding path-decomposition is given.

AB - 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 build a corresponding path-decomposition is given.

M3 - Article

SN - 0895-4801

VL - 6

SP - 181

EP - 188

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -

The Pathwidth and Treewidth of Cographs

Abstract

Fingerprint

Cite this