Hon-Chan Chen - Optimal Sequential and Parallel Algorithms for Cut Vertices and Bridges on Trapezoid Graphs

dmtcs:314 - Discrete Mathematics & Theoretical Computer Science, January 1, 2004, Vol. 6 no. 2 - https://doi.org/10.46298/dmtcs.314
Optimal Sequential and Parallel Algorithms for Cut Vertices and Bridges on Trapezoid GraphsArticle

Authors: Hon-Chan Chen 1

  • 1 Department of Information Management [Taichung]

Let G be a graph. A component of G is a maximal connected subgraph in G. A vertex v is a cut vertex of G if k(G-v) > k(G), where k(G) is the number of components in G. Similarly, an edge e is a bridge of G if k(G-e) > k(G). In this paper, we will propose new O(n) algorithms for finding cut vertices and bridges of a trapezoid graph, assuming the trapezoid diagram is given. Our algorithms can be easily parallelized on the EREW PRAM computational model so that cut vertices and bridges can be found in O(log n) time by using O(n / log n) processors.


Volume: Vol. 6 no. 2
Published on: January 1, 2004
Imported on: March 26, 2015
Keywords: cut vertex,bridge,trapezoid graph,algorithm,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 238 times.
This article's PDF has been downloaded 287 times.