Parallel Optimization Algorithms for Interval Graphs in BSP-like Models

Tuesday, May 13, 1997 - 9:30am - 10:30am
Vincent 570
Afonso Ferreira (CNRS-LIP ENS Lyon)
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.