Accession Number:

ADA172043

Title:

Applications of Parallel Scheduling to Perfect Graphs.

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Helmbold,David
• Mayr,Ernst W.

Report Date:

1986-06-01

Pagination or Media Count:

19.0

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.

Descriptors:

• *ALGORITHMS
• *SCHEDULING
• GRAPHS
• PARALLEL PROCESSING
• PERMUTATIONS
• MATCHING
• INTERVALS

Subject Categories:

Distribution Statement:

APPROVED FOR PUBLIC RELEASE