Optimal Sequential and Parallel Algorithms for Cut Vertices and Bridges on Trapezoid Graphs - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Journal Articles Discrete Mathematics and Theoretical Computer Science Year : 2004

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.
Fichier principal
Vignette du fichier
dm060220.pdf (132.13 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00959022 , version 1 (13-03-2014)

Identifiers

Cite

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

Collections

TDS-MACS
75 View
847 Download

Altmetric

Share

Gmail Facebook X LinkedIn More