DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click HERE
to register or log in.
Applications of Parallel Scheduling to Perfect Graphs.
STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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.
APPROVED FOR PUBLIC RELEASE