A fast parallel algorithm to recognize P4-sparse graphs

DOI10.1016/S0166-218X(97)00085-1zbMATH Open0894.68110WikidataQ127797600 ScholiaQ127797600MaRDI QIDQ1382265FDOQ1382265

Authors: Rong Lin, Stephan Olariu 

Publication date: 19 August 1998

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

Recommendations

• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs
• A tree representation for \(P_ 4\)-sparse graphs

zbMATH Keywords

cluster analysisschedulingautomated theorem provingmobile computingnetworkinggroup-based collaboration

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Cites Work

• Graph theory
• Title not available (Why is that?)
• Complement reducible graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• A tree representation for \(P_ 4\)-sparse graphs
• An optimal parallel matching algorithm for cographs
• Efficient parallel recognition algorithms of cographs and distance hereditary graphs
• A Linear Recognition Algorithm for Cographs
• On a class of posets and the corresponding comparability graphs
• The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• On a property of the class of n-colorable graphs
• Dacey Graphs
• Hamiltonicity in graphs with few \(P_ 4\)'s
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• P-Components and the Homogeneous Decomposition of Graphs
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs
• Parallel Algorithm for Cograph Recognition with Applications
• A linear-time recognition algorithm for \(P_{4}\)-reducible graphs
• Title not available (Why is that?)
• Isomorphism Testing in Hookup Classes
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (4)

• Efficient parallel recognition of cographs
• Some new classes of open distance-pattern uniform graphs
• Parallel algorithms for P4-comparability graphs
• An optimal parallel solution for the path cover problem on \(P_{4}\)-sparse graphs

This page was built for publication: A fast parallel algorithm to recognize P4-sparse graphs

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