Skip to Main content Skip to Navigation
Journal articles

Optimal Sequential and Parallel Algorithms for Cut Vertices and Bridges on Trapezoid Graphs

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-00959022
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, March 13, 2014 - 5:06:44 PM
Last modification on : Wednesday, November 29, 2017 - 10:26:20 AM
Long-term archiving on: : Friday, June 13, 2014 - 12:15:37 PM

File

dm060220.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00959022, version 1

Collections

Citation

Hon-Chan Chen. Optimal Sequential and Parallel Algorithms for Cut Vertices and Bridges on Trapezoid Graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2004, 6 (2), pp.483-496. ⟨hal-00959022⟩

Share

Metrics

Record views

147

Files downloads

878