BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-86-1118
       ENTRY:: May 01, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Applications of Parallel Scheduling to Perfect Graphs
        TYPE:: Technical Report
      AUTHOR:: Helmbold, David
      AUTHOR:: Mayr, Ernst
        DATE:: June 1986
       PAGES:: 20
    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.
       NOTES:: [Adminitrivia V1/Prg/19950501]
         END:: STAN//CS-TR-86-1118