descriptionPublicationkeyboard_double_arrow_right Part of book or chapter of book , Article 01 Jan 1990Publisher:Springer Berlin HeidelbergJournal:SIAM Journal on Discrete Mathematics, volume 6, pages 181-188 (issn: 0895-4801, eissn: 1095-7146,

Authors: Hans L. Bodlaender; Rolf H. Möhring;

doi: 10.1007/3-540-52846-6_99 , 10.1137/0406014

The pathwidth and treewidth of cographs

- Summary
- Subjects
- Metrics

Abstract

Summary: 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.

Related Organizations

Keywords

linear time algorithm, pathwidth, Trees, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, graph algorithm, treewidth, cograph

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	139
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 1%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%