\(P_ 4\)-trees and substitution decomposition (Q1201812)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: \(P_ 4\)-trees and substitution decomposition |
scientific article; zbMATH DE number 98504
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | \(P_ 4\)-trees and substitution decomposition |
scientific article; zbMATH DE number 98504 |
Statements
\(P_ 4\)-trees and substitution decomposition (English)
0 references
17 January 1993
0 references
Cotrees for cographs (\(P_ 4\)-free graphs) are generalized to \(P_ 4\)- trees, which can be used to give the modular decomposition of the graph. A vertex addition algorithm is given to construct the \(P_ 4\)-tree of an \(n\)-vertex \(m\)-edge graph in \(O(n+m)\) time. A second algorithm is then given to produce the modular decomposition of the graph in almost linear time. A very clear summary of the applications of modular decomposition is included.
0 references
substitution decomposition
0 references
cotrees
0 references
cographs
0 references
modular decomposition
0 references
0 references
0 references
