TY - GEN
T1 - Applications of parallel scheduling to perfect graphs
AU - Helmbold, David
AU - Mayr, Ernst
N1 - Publisher Copyright:
© 1987, Springer-Verlag.
PY - 1987
Y1 - 1987
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85023290836&partnerID=8YFLogxK
U2 - 10.1007/3-540-17218-1_59
DO - 10.1007/3-540-17218-1_59
M3 - Conference contribution
AN - SCOPUS:85023290836
SN - 9783540172185
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 188
EP - 203
BT - Graph-Theoretic Concepts in Computer Science - International Workshop, WG 1986, Proceedings
A2 - Schmidt, Gunther
A2 - Tinhofer, Gottfried
PB - Springer Verlag
T2 - 12th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1986
Y2 - 17 June 1986 through 19 June 1986
ER -