Applications of Parallel Scheduling to Perfect Graphs.

Abstract

The authors 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 maximum coloring problem for co-comparability graphs. These parallel algorithms can also be used to identify permutation graphs and interval graphs, important subclasses of perfect graphs.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1986
Accession Number
ADA172043

Entities

People

  • David Helmbold
  • Ernst W. Mayr

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Decomposition
  • Intervals
  • Iterations
  • Military Research
  • Orientation (Direction)
  • Parallel Computing
  • Permutations
  • Polynomials
  • Procedures (Computers)
  • Scheduling (Production)
  • Security
  • Sequences
  • Triangles

Readers

  • Graph Algorithms and Convex Optimization.