Abstract
Improved Approximation Algorithms for Embedding Hypergraphs in aCycle
by: Teofilo F. Gonzalez
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.
Keywords:
Approximation Algorithms, parallel computation, CAD, linear timealgorithms, minimize congestion
Date:
December 1997
Document: 1997-23
