Technical Report CS0830

TR#:CS0830
Class:CS
Title: EFFICIENT 2-SAT RELATED ROUTING TECHNIQUE.
Authors: R. Bar-Yehuda, J.A. Feldman and R. Kay
PDFNot Available
Abstract: We consider three wire-routing problems: one layer L-shape routing, restricted two layers L-shape routing, and two layers assignment of segments. We show how to construct a solution for a given set of n nets, if one exists. Traditionally, the solution scheme is based on transformation to 2-SAT or to graph 2-colorability. The known time bound for one layer L-shape routing and for two layers assignment is O(n^2); the non-restricted two layers L-shape routing is NP-complete. In this paper we present a novel technique which relies on limited branching and efficient geometrical data structures. We apply the technique for the routing problems, and prove that it yields almost linear time algorithms in the worst case.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1994/CS/CS0830), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1994
To the main CS technical reports page

Computer science department, Technion
admin