Constant-time parallel recognition of split graphs

DOI10.1016/0020-0190(94)00233-OzbMath0875.68684OpenAlexW2029489043WikidataQ126849116 ScholiaQ126849116MaRDI QIDQ1349719

Stavros D. Nikolopoulos

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00233-o

zbMATH Keywords

Parallel algorithmsSplit graphsPerfect graphsParallel recognition

Mathematics Subject Classification ID

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

Related Items

Recognizing cographs and threshold graphs through a classification of their edges ⋮ On complete systems of invariants for small graphs ⋮ Recognition of split-graphic sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel computation and conflicts in memory access
• Parallel concepts in graph theory
• Optimal bounds for decision problems on the CRCW PRAM
• Implementation of simultaneous memory address access in models that forbid it