For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Testing the Two-Layer Routability in a Circular Channel
Noriya KOBAYASHI Masahiro ABE Toshinobu KASHIWABARA Sumio MASUDA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1992/01/25
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Computer Aided Design (CAD)
algorithm, routing problem, via minimization,
Full Text: PDF>>
Suppose that there are terminals on two concentric circles Cin and Cout, with Cin inside of Cout. A set of two-terminal nets is given and the routing area is the annular region between the two circles. In this paper, we present an O(n2) time algorithm for testing whether the given net set is two-layer routable, where n is the number of nets. Applying this algorithm repeatedly, we can find, in O(n3) time, a maximal subset of nets which is two-layer routable.