Parallel recognition of complement reducible graphs and cotree construction

DOI10.1016/0166-218X(90)90083-OzbMath0707.68039MaRDI QIDQ919826

David G. Kirkpatrick, Teresa M. Przytycka

Publication date: 1990

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

zbMATH Keywords

parallel algorithm; cographs; CREW PRAM; parse tree representation

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68N20: Theory of compilers and interpreters

68P05: Data structures

68W15: Distributed algorithms

Related Items

On parallel recognition of cographs, A theorem on permutation graphs with applications, Minimax trees in linear time with applications, A faster parallel connectivity algorithm on cographs, Efficient parallel recognition of cographs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel recognition and decomposition of two terminal series parallel graphs
• The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
• Complement reducible graphs
• On a class of posets and the corresponding comparability graphs
• A Linear Recognition Algorithm for Cographs
• Computing connected components on parallel computers
• Dacey Graphs
• The Parallel Evaluation of General Arithmetic Expressions
• A simple parallel tree contraction algorithm