Report ID
1997-23
Report Authors
Teofilo F. Gonzalez
Report Date
Abstract
Approximation algorithms embedding hypergraphs in a cycle so as to minimize themaximum congestion are presented. Our algorithms generate an embedding bytransforming the problem into another problem that can be solved in polynomialtime. One transforms it to a Linear Programming (LP) problem, and the otherone (LP-Free) to the problem of embedding a graph in a cycle. Both algorithmsgenerate an embedding with congestion at most twice of that in an optimalsolution, and we give problem instances for which the solutions generated byboth of these algorithms is about twice of optimal. Our problem hasapplications in CAD and parallel computation.
Document
1997-23.ps134.77 KB