A linear-time recognition algorithm for P₄-reducible graphs

DOI10.1016/0304-3975(95)00016-PMaRDI QIDQ673108zbMATHOpenAlexFDO

Authors Juan-Miguel Gracia

Publication date 28 February 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(95)00016-p

zbMATH Keywords

cographs\(P_ 4\)-reducible graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 4206028
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs

Cites work

• scientific article; zbMATH DE number 4206028 (Why is no real title available?)
• scientific article; zbMATH DE number 3920497 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A Linear Recognition Algorithm for Cographs
• Complement reducible graphs
• Dacey Graphs
• Incremental modular decomposition
• On a class of posets and the corresponding comparability graphs
• On a property of the class of n-colorable graphs

Cited in

(19)

• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• The graph sandwich problem for \(P_4\)-sparse graphs
• A fast parallel algorithm to recognize P4-sparse graphs
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• Algorithms for \(P_4\)-comparability graph recognition and acyclic \(P_4\)-transitive orientation
• On bipartite graphs with weak density of some subgraphs
• On some domination colorings of graphs
• scientific article; zbMATH DE number 7740902 (Why is no real title available?)
• Cross-series-parallel digraphs
• scientific article; zbMATH DE number 2081001 (Why is no real title available?)
• Efficiently recognizing the \(P_4\)-structure of trees and of bipartite graphs without short cycles
• Path-bicolorable graphs
• On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
• A representation for the modular-pairs of a P4-reducible graph by modular decomposition
• On the clique-width of graph with few \(P_{4}\)'s
• Path-bicolorable graphs. (Extended abstract)
• Linear time recognition of \(P_4\)-indifference graphs
• scientific article; zbMATH DE number 4206028 (Why is no real title available?)
• Efficient parallel recognition of cographs

This page was built for publication: A linear-time recognition algorithm for \(P_{4}\)-reducible graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q673108)