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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2004, 6 (2), pp.483-496
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00959022
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 17:06:44
Dernière modification le : mercredi 29 novembre 2017 - 10:26:20
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:15:37

Fichier

dm060220.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

101

Téléchargements de fichiers

300