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

DOI10.1016/0020-0190(92)90244-PMaRDI QIDQ1198065zbMATH OpenOpenAlexFDO

Authors 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

blocksbridgescut verticesinterval graphparallel 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)

Recommendations

• An optimal parallel algorithm for computing cut vertices and blocks on interval graphs
• Parallel algorithms on interval graphs
• Parallel algorithms for connectivity problems on interval graphs
• An optimal parallel algorithm to compute all cutvertices and blocks on permutation graphs
• scientific article; zbMATH DE number 2159654

Cites work

• An Efficient Parallel Biconnectivity Algorithm
• Binary Trees and Parallel Scheduling Algorithms
• Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4155887 (Why is no real title available?)
• scientific article; zbMATH DE number 3637904 (Why is no real title available?)
• Parallel concepts in graph theory
• Parallel Merge Sort
• Some parallel algorithms on interval graphs

Cited in

(12)

• A parallel algorithm for finding minimum cutsets in reducible graphs
• Parallel algorithms for connectivity problems on interval graphs
• Optimal sequential and parallel algorithms to compute all cut vertices on trapezoid graphs
• An efficient algorithm to solve connectivity problem on trapezoid graphs
• Parallel algorithms on interval graphs
• An optimal parallel algorithm for computing cut vertices and blocks on interval graphs
• scientific article; zbMATH DE number 2159654 (Why is no real title available?)
• PARALLEL BLOCK-FINDING USING DISTANCE MATRICES
• Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph
• An optimal parallel algorithm to compute all cutvertices and blocks on permutation graphs
• A self-stabilizing algorithm for finding articulation points
• A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs

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

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