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

DOI10.1080/00207160008804965zbMath0960.68132MaRDI 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

block; analysis of algorithms; design of algorithms; interval graph; cut vertex

Mathematics Subject Classification ID

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

68W10: Parallel algorithms in computer science

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item