An optimal parallel algorithm for computing cut vertices and blocks on interval graphs

DOI10.1080/00207160008804965zbMath0960.68132OpenAlexW2154421125MaRDI QIDQ4498117

Madhumangal Pal, Debashis Bera, Sukumar Mondal, Tapan Kumar Pal

Publication date: 24 August 2000

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

Full work available at URL: https://doi.org/10.1080/00207160008804965

zbMATH Keywords

blockanalysis of algorithmsdesign of algorithmsinterval graphcut vertex

Mathematics Subject Classification ID

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

Related Items (6)

A linear time algorithm to compute square of interval graphs and their colouring ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ Minimum 2-tuple dominating set of an interval graph ⋮ Finding outer-connected dominating sets in interval graphs ⋮ \(L(2,1)\)-labeling of interval graphs ⋮ An optimal parallel algorithm to compute all cutvertices and blocks on permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding biconnected components in O(n) time for a class of graphs
• One-dimensional logic gate assignment and interval graphs
• Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
• An Efficient Parallel Biconnectivity Algorithm

This page was built for publication: An optimal parallel algorithm for computing cut vertices and blocks on interval graphs