Paper Info
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 m processors and the modular decomposition algorithm runs in O(log n) time using n 3 processors (n, m and respectively denote the number of vertices, the number of edges and the maximal degree of the undirected input graph).
Year
DOI
Venue
1996
10.1007/3-540-60922-9_15
STACS
Keywords
Field
DocType
parallel comparability graph recognition,modular decomposition,parallel algorithm,parallel random access machine
Discrete mathematics,Complete graph,Binary logarithm,Comparability graph,Combinatorics,Modular decomposition,Vertex (geometry),Parallel random-access machine,Parallel algorithm,Computer science,Trivially perfect graph
Conference
ISBN
Citations 
PageRank 
3-540-60922-9
1
0.35
References 
Authors
5
2
Name
Order
Citations
PageRank
Michel Morvan121133.41
Laurent Viennot249235.31