Parallel recognition of complement reducible graphs and cotree construction

DOI10.1016/0166-218X(90)90083-OMaRDI QIDQ919826zbMATH OpenFDO

Authors David Kirkpatrick, Teresa Przytycka

Publication date 1990

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

Full work available at URL https://doi.org/10.1016/0166-218X(90)90083-O

zbMATH Keywords

parallel algorithmcographsCREW PRAMparse tree representation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Theory of compilers and interpreters (68N20) Distributed algorithms (68W15)

Recommendations

• Efficient parallel recognition of cographs
• Parallel algorithm for cograph recognition with applications
• Parallel Algorithm for Cograph Recognition with Applications
• Efficient parallel recognition algorithms of cographs and distance hereditary graphs
• scientific article; zbMATH DE number 4213472

Cites work

• scientific article; zbMATH DE number 3889564 (Why is no real title available?)
• scientific article; zbMATH DE number 4011928 (Why is no real title available?)
• scientific article; zbMATH DE number 4064468 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A simple parallel tree contraction algorithm
• Complement reducible graphs
• Computing connected components on parallel computers
• Dacey Graphs
• On a class of posets and the corresponding comparability graphs
• Parallel recognition and decomposition of two terminal series parallel graphs
• The Parallel Evaluation of General Arithmetic Expressions
• The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time

Cited in

(14)

• Parallel algorithms for cographs and parity graphs with applications
• Efficient parallel recognition of cographs
• Parallel Algorithm for Cograph Recognition with Applications
• Parallel algorithm for cograph recognition with applications
• An efficient reconstruction of a graph from its line graph in parallel
• A simple parallel tree contraction algorithm
• scientific article; zbMATH DE number 140480 (Why is no real title available?)
• A theorem on permutation graphs with applications
• On parallel recognition of cographs
• Minimax trees in linear time with applications
• A fast parallel algorithm to recognize partitionable graphs
• A faster parallel connectivity algorithm on cographs
• scientific article; zbMATH DE number 3920497 (Why is no real title available?)
• Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs

This page was built for publication: Parallel recognition of complement reducible graphs and cotree construction

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