Parallel Algorithm for Cograph Recognition with Applications

DOI10.1006/JAGM.1993.1042MaRDI QIDQ3141534zbMATH OpenOpenAlexFDO

Authors Xin He

Publication date 6 December 1993

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/762222b3818f0770adc4e72960e910307d063f76

zbMATH Keywords

parallel algorithmpermutation representationcographspermutation graphsmaximum matchingCRCW PRAMcotreesdepth-first spanning tree

Mathematics Subject Classification ID

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

Recommendations

• Parallel algorithm for cograph recognition with applications
• Efficient parallel recognition of cographs
• scientific article; zbMATH DE number 4213472
• Parallel recognition of complement reducible graphs and cotree construction
• On parallel recognition of cographs

Cited in

(22)

• A fast parallel algorithm to recognize P4-sparse graphs
• Parallel algorithms for cographs and parity graphs with applications
• scientific article; zbMATH DE number 3896983 (Why is no real title available?)
• Efficient parallel recognition of cographs
• Parallel algorithms for parity graphs
• A time-optimal solution for the path cover problem on cographs.
• Parallel algorithm for cograph recognition with applications
• An efficient reconstruction of a graph from its line graph in parallel
• scientific article; zbMATH DE number 140480 (Why is no real title available?)
• An optimal parallel matching algorithm for cographs
• Competitive graph searches
• Efficient parallel modular decomposition (extended abstract)
• Efficient parallel recognition algorithms of cographs and distance hereditary graphs
• A theorem on permutation graphs with applications
• On parallel recognition of cographs
• Parallel recognition of complement reducible graphs and cotree construction
• A fast parallel algorithm to recognize partitionable graphs
• A faster parallel connectivity algorithm on cographs
• An NC algorithm for the clique cover problem in cocomparability graphs and its application
• A simple linear time algorithm for cograph recognition
• Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
• Parallel comparability graph recognition and modular decomposition

This page was built for publication: Parallel Algorithm for Cograph Recognition with Applications

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