Testing the Two-Layer Routability in a Circular Channel

Noriya KOBAYASHI; Masahiro ABE; Toshinobu KASHIWABARA; Sumio MASUDA

Testing the Two-Layer Routability in a Circular Channel

Noriya KOBAYASHI, Masahiro ABE, Toshinobu KASHIWABARA, Sumio MASUDA

Full Text Views

0

Share
Cite this

Summary :

Suppose that there are terminals on two concentric circles C_in and C_out, with C_in inside of C_out. 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(n²) 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(n³) time, a maximal subset of nets which is two-layer routable.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E75-A No.1 pp.83-91

Publication Date: 1992/01/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Computer Aided Design (CAD)

Cite this

Copy

Noriya KOBAYASHI, Masahiro ABE, Toshinobu KASHIWABARA, Sumio MASUDA, "Testing the Two-Layer Routability in a Circular Channel" in IEICE TRANSACTIONS on Fundamentals, vol. E75-A, no. 1, pp. 83-91, January 1992, doi: .
Abstract: Suppose that there are terminals on two concentric circles C_in and C_out, with C_in inside of C_out. 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(n²) 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(n³) time, a maximal subset of nets which is two-layer routable.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e75-a_1_83/_p

Copy

@ARTICLE{e75-a_1_83,
author={Noriya KOBAYASHI, Masahiro ABE, Toshinobu KASHIWABARA, Sumio MASUDA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Testing the Two-Layer Routability in a Circular Channel},
year={1992},
volume={E75-A},
number={1},
pages={83-91},
abstract={Suppose that there are terminals on two concentric circles C_in and C_out, with C_in inside of C_out. 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(n²) 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(n³) time, a maximal subset of nets which is two-layer routable.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Testing the Two-Layer Routability in a Circular Channel
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 83
EP - 91
AU - Noriya KOBAYASHI
AU - Masahiro ABE
AU - Toshinobu KASHIWABARA
AU - Sumio MASUDA
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E75-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1992
AB - Suppose that there are terminals on two concentric circles C_in and C_out, with C_in inside of C_out. 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(n²) 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(n³) time, a maximal subset of nets which is two-layer routable.
ER -