Interval graphs are useful in modeling many practical applications, such as in genetics, ecology, archaeology, scheduling, channel assignment, VLSI design, file organization, code optimization and establishing ring protocols.

Because of its importance, this class of graphs has been extensively studied on the PRAM model. In this talk we show parallel algorithms for the BSP and CGM models, to solve some important problems arising in interval graphs, as connected components, maximum weighted clique, BFS and DFS tree, minimum coloring and others.

All our algorithms take a very small number of communication rounds: either constant or O(log p). This is joint work with K. Marcus and A. Rau-Chaplin.

Back to Workshop Schedule

1996-1997 Mathematics in High Performance Computing