Finding biconnected components in O(n) time for a class of graphs

DOI10.1016/S0020-0190(96)00153-6zbMath0875.68707OpenAlexW2010357409MaRDI QIDQ1350120

Y. Daniel Liang, Chongkye Rhee

Publication date: 27 February 1997

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(96)00153-6

zbMATH Keywords

AlgorithmsBreadth-first searchBiconnected component

Mathematics Subject Classification ID

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

Related Items

An optimal parallel algorithm to compute all cutvertices and blocks on permutation graphs ⋮ Unrestricted and complete breadth-first search of trapezoid graphs in \(O(n)\) time ⋮ An optimal parallel algorithm for computing cut vertices and blocks on interval graphs

Cites Work

• Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
• Why should biconnected components be identified first
• Unnamed Item