From parallel comparability graph recognition and modular decomposition - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 1996

From parallel comparability graph recognition and modular decomposition

Résumé

A parallelization of the algorithm of Golumbic for recognizing comparability graphs is proposed for the concurrent parallel random access machine (CRCW PRAM). Parallel algorithms for finding a transitive orientation and the modular decomposition of any undirected graph are deduced from an extension of the theory of Golumbic toward modular decomposition. The algorithms for recognizing and transitively orienting comparability graphs run in O(log n) time using d m processors and the modular decomposition algorithm runs in O(log n) time using n^3 processors (n, m and d respectively denote the number of vertices, the number of edges and the maximal degree of the undirected input graph).
Fichier principal
Vignette du fichier
stacs96.pdf (200.37 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00471608 , version 1 (08-04-2010)

Identifiants

Citer

Michel Morvan, Laurent Viennot. From parallel comparability graph recognition and modular decomposition. 13th Symposium on Theoretical Aspects of Computer Science (STACS), 1996, Grenoble, France. pp.169-180, ⟨10.1007/3-540-60922-9_15⟩. ⟨inria-00471608⟩
55 Consultations
232 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More