Parallel Algorithms for Maximum Independent Set in Trapezoid Graphs and their Applications
Presentation
Overview
Overview
Description
Given a set of signal nets with terminals labeled on the upper and lower side of a two-sided channel in
a VLSI chip, one of the goals of channel routing is to route the signal nets using fewest number of layers.
A pair of signal nets when modeled by trapezoids, connecting the right most and left most terminals
on the upper and lower side of a channel, can be routed on the same layer without interference i® the
corresponding trapezoids do not intersect.
The intersection relationship between trapezoids is represented by a graph called 'trapezoid graph' and the
solutions to the maximum independent set and maximum clique problems form the basis for the channel
routing of signal nets.
Although, sequential algorithms to solve maximum independent set and maximum clique problems in
trapezoid graphs are known [1], the sweep line approach employed by the sequential algorithm is incre-
mental in nature and does not yield itself to a parallel solution. In this paper we present several new
ideas which make the parallel algorithm possible.
The total work done by the parallel algorithms is comparable to the work done by the best known sequential
algorithms [1] for the two problems. In this sense our algorithms are considered to be e±cient.
