From parallel comparability graph recognition and modular decomposition

Abstract : 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).
Type de document :
Communication dans un congrès
Claude Puech. 13th Symposium on Theoretical Aspects of Computer Science (STACS), 1996, Grenoble, France. Springer Berlin / Heidelberg, 1046, pp.169-180, 1996, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/p2882577874p552g/〉. 〈10.1007/3-540-60922-9_15〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00471608
Contributeur : Laurent Viennot <>
Soumis le : jeudi 8 avril 2010 - 16:13:15
Dernière modification le : mercredi 21 mars 2018 - 18:57:38
Document(s) archivé(s) le : vendredi 9 juillet 2010 - 21:17:37

Fichiers

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

Identifiants

Collections

Citation

Michel Morvan, Laurent Viennot. From parallel comparability graph recognition and modular decomposition. Claude Puech. 13th Symposium on Theoretical Aspects of Computer Science (STACS), 1996, Grenoble, France. Springer Berlin / Heidelberg, 1046, pp.169-180, 1996, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/p2882577874p552g/〉. 〈10.1007/3-540-60922-9_15〉. 〈inria-00471608〉

Partager

Métriques

Consultations de la notice

83

Téléchargements de fichiers

149