Constant-time parallel recognition of split graphs

DOI10.1016/0020-0190(94)00233-OMaRDI QIDQ1349719zbMATH OpenOpenAlexWikidataFDO

Authors 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 algorithmsParallel recognitionPerfect graphsSplit graphs

Mathematics Subject Classification ID

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

Recommendations

• A fast parallel algorithm to recognize partitionable graphs
• A note on the recognition of bisplit graphs
• Efficient parallel recognition of cographs
• Parallel recognition of series-parallel graphs
• Efficient parallel recognition algorithms of cographs and distance hereditary graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4147494 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• Implementation of simultaneous memory address access in models that forbid it
• Optimal bounds for decision problems on the CRCW PRAM
• Parallel computation and conflicts in memory access
• Parallel concepts in graph theory

Cited in

(5)

• Recognition of split-graphic sequences
• A note on the recognition of bisplit graphs
• Recognizing cographs and threshold graphs through a classification of their edges
• On complete systems of invariants for small graphs
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition

This page was built for publication: Constant-time parallel recognition of split graphs

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