Title :
A parallel algorithm for maximum independent set of a circular-arc graph
Author :
Sprague, Alan P.
Author_Institution :
Dept. of Comput. & Inf. Sci., Alabama Univ., Birmingham, AL, USA
Abstract :
The author presents a parallel algorithm of cost O(n log n) to find a maximum independent set of a circular arc graph. In the CREW PRAM model the algorithm takes O(log n) time, while in the EREW PRAM model it requires O(log2 n) time. It illustrates the use of divide-and-conquer in parallel algorithms. The heart of the algorithm solves this problem on an interval graph, which is derived from the given circular arc graph. Postprocessing selects a maximum independent set on the given circular arc graph
Keywords :
graph theory; parallel algorithms; set theory; CREW PRAM model; EREW PRAM model; circular-arc graph; cost; divide-and-conquer; maximum independent set; parallel algorithm; postprocessing; Concurrent computing; Costs; Greedy algorithms; Heart; Parallel algorithms; Phase change random access memory; Polynomials; Zirconium;
Conference_Titel :
Southeastcon '92, Proceedings., IEEE
Conference_Location :
Birmingham, AL
Print_ISBN :
0-7803-0494-2
DOI :
10.1109/SECON.1992.202301
