IEICE TRANSACTIONS on Fundamentals
Testing the Two-Layer Routability in a Circular Channel
Summary :
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.
- 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)
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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 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.
URL: https://global.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 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.},
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 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.
ER -
English
