PARALLEL RECOGNITION ALGORITHMS FOR GRAPHS WITH RESTRICTED NEIGHBOURHOODS

DOI10.1142/S0129054190000102zbMATH Open0726.68035OpenAlexW2015408755MaRDI QIDQ3348414FDOQ3348414

Authors: Sergio De Agostino, Rossella Petreschi 

Publication date: 1990

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054190000102

Recommendations

• A fast parallel algorithm to recognize partitionable graphs
• Parallel recognition of series-parallel graphs
• Parallel comparability graph recognition and modular decomposition
• Efficient parallel recognition algorithms of cographs and distance hereditary graphs
• Efficient parallel recognition of some circular arc graphs. I

zbMATH Keywords

threshold graphsdegree sequencesparallel recognition algorithms

Mathematics Subject Classification ID

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

Cited In (4)

• Efficient parallel recognition of cographs
• Threshold graphs and synchronization protocols
• Recognizing cographs and threshold graphs through a classification of their edges
• Parallel algorithms for Hamiltonian problems on quasi-threshold graphs

This page was built for publication: PARALLEL RECOGNITION ALGORITHMS FOR GRAPHS WITH RESTRICTED NEIGHBOURHOODS

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