Main navigation | Main content

HOME » PROGRAMS/ACTIVITIES » Annual Thematic Program

PROGRAMS/ACTIVITIES

Annual Thematic Program »Postdoctoral Fellowships »Hot Topics and Special »Public Lectures »New Directions »PI Programs »Math Modeling »Seminars »Be an Organizer »Annual »Hot Topics »PI Summer »PI Conference »Applying to Participate »

Talk Abstract

Parallel optimization algorithms for interval graphs in BSP-like models

Parallel optimization algorithms for interval graphs in BSP-like models

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