S. Gao
K. Mehlhorn
ABSTRACT
We give an Ο(n3·log n) time and Ο(n3) space algorithm for the continuous homotopic one layer routing problem. The main contribution is an extension of the sweep paradigm to a universal cover space of the plane.
- CS.R. Cole and A. Siegel, "River Routing every which way, but loose," 24th Annum Symposium on Foundations of Computer Science (November 1983), pp. 112-121.Google Scholar
- LM.C. E. Leiserson and F. M. Maley, "Algorithms for Routing and Testing Routability of Planar VLSI Layouts", 17th Annual ACM Symposium on Theory of Computing (May 1985), pp. 69- 78. Google ScholarDigital Library
- M.F.M. Maley, "Single-Layer Wire Routing", Ph. D. Thesis, Massachusetts Institute of Technology, August 1987.Google Scholar
- ST.H. Seifert and W. Threlfall, "Lehrbuch der Topologie", Chelsea Publishing Company, 1947.Google Scholar
- T.M. Tompa, "An Optimal Solution to a Wire- Routing Problem", Journal of Computer and System Sciences 23, pp. 127-150.Google ScholarCross Ref
Index Terms
- On continuous Homotopic one layer routing
Recommendations
A generic algorithm for one-dimensional homotopic compaction
AbstractOne-dimensional homotopic compaction problems model the task of VLSI layout compaction with automatic jog insertion. They have the following form: given a routable layout, find a layout of minimum width reachable by a continuous motion of layout ...
Computing homotopic shortest paths in the plane
We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. Problems on homotopy of paths received attention very recently [Cabello et al., in: Proc. 18th Annu. ACM Sympos. Comput. Geom., 2002, pp. 160-169; ...
Computing homotopic shortest paths in the plane
SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithmsWe address the problem of computing homotopic shortest paths in presence of obstacles in the plane. The problems on homotopy of the paths received attention very recently [3, 8]. We present two output-sensitive algorithms, for simple paths and non-...
Comments