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 algorithmcographsCREW PRAMparse tree representation

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item