Optimal parallel algorithms for finding cut vertices and bridges of interval graphs

DOI10.1016/0020-0190(92)90244-PzbMath0764.68054OpenAlexW2048724082MaRDI QIDQ1198065

Alan P. Sprague, K. H. Kulkarni

Publication date: 16 January 1993

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

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90244-p

zbMATH Keywords

blocksinterval graphbridgescut verticesparallel prefix algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (7)

Parallel algorithms for connectivity problems on interval graphs ⋮ PARALLEL BLOCK-FINDING USING DISTANCE MATRICES ⋮ Parallel algorithms on interval graphs ⋮ An efficient algorithm to solve connectivity problem on trapezoid graphs ⋮ An optimal parallel algorithm to compute all cutvertices and blocks on permutation graphs ⋮ A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs ⋮ A SELF-STABILIZING ALGORITHM FOR FINDING ARTICULATION POINTS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some parallel algorithms on interval graphs
• Parallel concepts in graph theory
• Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
• Binary Trees and Parallel Scheduling Algorithms
• An Efficient Parallel Biconnectivity Algorithm
• Parallel Merge Sort

This page was built for publication: Optimal parallel algorithms for finding cut vertices and bridges of interval graphs