Optimal Parallel Algorithm for the Maximum Clique Problem in a Family of Proper Circular Arcs
Auteur : Simon Fraser University. Centre for Systems Science
Date de publication : 1994
Éditeur : Simon Fraser University, Centre for Systems Science
Nombre de pages : 33
Résumé du livre
Proper circular arcs have applications in traffic control, cyclic scheduling, and compiler design. Given a family of simple and proper circular arcs, it is required to identify a largest cardinality subset, all of whose members intersect. This paper describes a parallel algorithm to solve this problem on the Concurrent Read Exclusive Write Parallel Random Access Machine (CREW PRAM) model of computation. The algorithm uses O(n/log n) processors and requires O(log n) time. The paper provides the theoretical background to the algorithm and includes example problems.