Report Number: CS-TR-86-1118
Institution: Stanford University, Department of Computer Science
Title: Applications of Parallel Scheduling to Perfect Graphs
Author: Helmbold, David
Author: Mayr, Ernst
Date: June 1986
Abstract: We combine a parallel algorithm for the two processor scheduling problem, which runs in polylog time on a polynomial number of processors, with an algorithm to find transitive orientations of graphs where they exist. Both algorithms together solve the maximum clique problem and the minimum coloring problem for comparability graphs, and the maximum matching problem for co-comparability graphs. These parallel algorithms can also be used to identify permutation graphs and interval graphs, important subclasses of perfect graphs.