research-article

The Via Minimization Problem is NP-Complete

Authors:

N. J. Naclerio,

K. NakajimaAuthors Info & Claims

IEEE Transactions on Computers, Volume 38, Issue 11

Pages 1604 - 1608

https://doi.org/10.1109/12.42135

Published: 01 November 1989 Publication History

Abstract

The authors analyze the computational complexity of the constrained via minimization problem. Given an already routed circuit, the problem is to find a minimum cardinality set of vias for which a valid layer assignment exists using only two layers. The authors first prove that the corresponding decision problem is NP-complete. They then show that it remains NP-complete even if one or more of the following restrictions are imposed: (1) the input layout must conform to a rectangular grid; (2) vias are restricted to lie at junctions which existed in the input layout; and (3) the maximum junction degree is limited to six or more.

References

[1]

{1} K. C. Chang and D. H-C. Du, "Efficient algorithms for layer assignment problem," IEEE Trans. Comput.-Aided Design, vol. CAD-6, no. 1, pp. 67-78, Jan. 1987.

[2]

{2} R-W. Chen, Y. Kajitani, and S-P. Chan, "A graph-theoretic via minimization algorithm for two-layer primed circuit boards," IEEE Trans. Circuits Syst., vol. CAS-30, no. 5, pp. 284-299, May 1983.

[3]

{3} N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa, "A linear time algorithm for embedding planar graphs using PQ-trees," J. Comput. Syst. Sci., vol. 30, pp. 54-76, 1985.

Digital Library

[4]

{4} M. J. Cielielski and E. Kinnen, "An optimum layer assignment for routing in ICs and PCBs," in Proc. 18th Design Automat. Conf., Nashville, TN, June 1981, pp. 733-737.

Digital Library

[5]

{5} I. Fary, "On straight line representation of planar graphs," Acta Sci. Math. (Szeged), vol. 11, pp. 229-233, 1948.

[6]

{6} M. R. Garey and D. S. Johnson, "The rectilinear Steiner tree problem is NP-complete," SIAM J. Appl. Math., vol. 32, no. 4, pp. 826-834, June 1977.

Digital Library

[7]

{7} M. R. Garey, D. S. Johnson, and L. Stockmeyer, "Some simplified NP-complete graph problems," Theoret. Comput. Sci., vol. 1, pp. 237-267, 1976.

[8]

{8} M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, CA: Freeman, 1979.

Digital Library

[9]

{9} A. Hashimoto and J. Stevens, "Wire routing by optimizing channel assignment within large apertures," in Proc. 8th Design Automat. Workshop, Atlantic City, NJ, June 1971, pp. 155-169.

Digital Library

[10]

{10} C.-P. Hsu, "Minimum via topological routing," IEEE Trans. Comput.-Aided Design, vol. CAD-2, no. 4, pp. 235-246, Oct. 1983.

[11]

{11} Y. Kajitani, "On via hole minimization of routing on a 2-layer board," in Proc. 1980 IEEE Int. Conf. Circuits Comput., Oct. 1980, pp. 295-298.

[12]

{12} M. Marek-Sadowska, "An unconstrained topological via minimization problem for two-layer routing," IEEE Trans. Comput.-Aided Design , vol. CAD-3, no. 3, pp. 184-190, July 1984.

[13]

{13} P. Molitor, "On the contact minimization problem," in Proc. 4th Annu. Symp. Theoret. Aspects Comput. Sci., Passau, West Germany, Feb. 1987, pp. 420-431.

Digital Library

[14]

{14} N. J. Naclerio, S. Masuda, and K. Nakajima, "Via minimization for gridless layouts," in Proc. 24th Design Automat. Conf., Miami Beach, FL, June 1987, pp. 159-165.

Digital Library

[15]

{15} R. Y. Pinter, "Optimal layer assignment for interconnect," in Proc. 1982 IEEE Int. Conf. Circuits Comput., New York, NY, Sept. 1982, pp. 398-401.

[16]

{16} K. R. Stevens and W. M. VanCleemput, "Global via elimination in generalized routing environment," in Proc. IEEE 1979 Int. Symp. Circuits Syst., Tokyo, Japan, June 1979, pp. 689-692.

[17]

{17} R. Tamassia, "On embedding a graph in the grid with the minimum number of bends," SIAM J. Comput., vol. 16, no. 3, pp. 421-444, June 1987.

Digital Library

Cited By

Lu RZhang WJiang LLiu G(2023)Slew-Driven Layer Assignment for Advanced Non-default-rule WiresWeb Information Systems and Applications10.1007/978-981-99-6222-8_45(539-550)Online publication date: 15-Sep-2023
https://dl.acm.org/doi/10.1007/978-981-99-6222-8_45
Han SLiu WEwetz RKoh CChao KWang T(2017)Delay-driven layer assignment for advanced technology nodes2017 22nd Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASPDAC.2017.7858365(456-462)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.1109/ASPDAC.2017.7858365
Yu BLiu DChowdhury SPan DMarculescu DLiu F(2015)TILAProceedings of the IEEE/ACM International Conference on Computer-Aided Design10.5555/2840819.2840835(110-117)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.5555/2840819.2840835
Show More Cited By

Index Terms

The Via Minimization Problem is NP-Complete

Recommendations

Infeasibility of instance compression and succinct PCPs for NP

The OR-SAT problem asks, given Boolean formulae @f"1,...,@f"m each of size at most n, whether at least one of the @f"i's is satisfiable. We show that there is no reduction from OR-SAT to any set A where the length of the output is bounded by a ...
Splitting NP-Complete Sets

We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long-standing open question in a surprising way. As a consequence of this unconditional result and recent work by Glaßer et al., complete sets for all of the following ...
Layer Assignment Problem for Three-Layer Routing

The layer assignment problem for interconnect is the problem of determining which layers should be used for wiring the signal nets so that the number of vias is minimized. The problem is often referred to as the via minimization problem. The problem is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 38, Issue 11

November 1989

136 pages

ISSN:0018-9340

Editor:
Ming T. Liu
Ohio State Univ., Columbus, OH

Issue’s Table of Contents

Copyright © Copyright © 1989 IEEE. All Rights Reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 November 1989

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lu RZhang WJiang LLiu G(2023)Slew-Driven Layer Assignment for Advanced Non-default-rule WiresWeb Information Systems and Applications10.1007/978-981-99-6222-8_45(539-550)Online publication date: 15-Sep-2023
https://dl.acm.org/doi/10.1007/978-981-99-6222-8_45
Han SLiu WEwetz RKoh CChao KWang T(2017)Delay-driven layer assignment for advanced technology nodes2017 22nd Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASPDAC.2017.7858365(456-462)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.1109/ASPDAC.2017.7858365
Yu BLiu DChowdhury SPan DMarculescu DLiu F(2015)TILAProceedings of the IEEE/ACM International Conference on Computer-Aided Design10.5555/2840819.2840835(110-117)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.5555/2840819.2840835
Liu WLi YHu JKoh C(2012)Optimizing the antenna area and separators in layer assignment of multi-layer global routingProceedings of the 2012 ACM international symposium on International Symposium on Physical Design10.1145/2160916.2160946(137-144)Online publication date: 25-Mar-2012
https://dl.acm.org/doi/10.1145/2160916.2160946
Liu WLi Y(2011)Negotiation-based layer assignment for via count and via overflow minimizationProceedings of the 16th Asia and South Pacific Design Automation Conference10.5555/1950815.1950924(539-544)Online publication date: 25-Jan-2011
https://dl.acm.org/doi/10.5555/1950815.1950924
Dai KLiu WLi YWakabayashi K(2009)Efficient simulated evolution based rerouting and congestion-relaxed layer assignment on 3-D global routingProceedings of the 2009 Asia and South Pacific Design Automation Conference10.5555/1509633.1509767(570-575)Online publication date: 19-Jan-2009
https://dl.acm.org/doi/10.5555/1509633.1509767
Cho MLu KYuan KPan D(2009)BoxRouter 2.0ACM Transactions on Design Automation of Electronic Systems10.1145/1497561.149757514:2(1-21)Online publication date: 7-Apr-2009
https://dl.acm.org/doi/10.1145/1497561.1497575
Cho MLu KYuan KPan DGielen G(2007)BoxRouter 2.0Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design10.5555/1326073.1326176(503-508)Online publication date: 5-Nov-2007
https://dl.acm.org/doi/10.5555/1326073.1326176
Lin RChen S(2007)Conjugate conflict continuation graphs for multi-layer constrained via minimizationInformation Sciences: an International Journal10.1016/j.ins.2007.01.013177:12(2436-2447)Online publication date: 20-Jun-2007
https://dl.acm.org/doi/10.1016/j.ins.2007.01.013
Tang M(2005)An adaptive genetic algorithm for the minimal switching graph problemProceedings of the 5th European conference on Evolutionary Computation in Combinatorial Optimization10.1007/978-3-540-31996-2_21(224-233)Online publication date: 30-Mar-2005
https://dl.acm.org/doi/10.1007/978-3-540-31996-2_21
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents