Rapport de Recherche Litp /
Litp research reports
19 pages - Juillet/July 1995 - Document en anglais.
PostScript : Ko /Kb
Titre / Title: 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 dm processors and the modular decomposition algorithm runs in O(log n) time using n3 processors. n, m and d respectively denote the number of vertices, the number of edges and the maximal degree of the undirected input graph.
Publications internes Litp 1995 / Litp research reports 1995