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

DOI10.1016/0304-3975(95)00016-PzbMATH Open0873.68155OpenAlexW2038893115MaRDI QIDQ673108FDOQ673108

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

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

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)

Cites Work

• Complement reducible graphs
• Title not available (Why is that?)
• A Linear Recognition Algorithm for Cographs
• Incremental modular decomposition
• On a class of posets and the corresponding comparability graphs
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• On a property of the class of n-colorable graphs
• Dacey Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (19)

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

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)