NDLI: Solving constrained via minimization by compact linear programming

Content Provider	IEEE Xplore Digital Library
Author	Shi, C.-J.R.
Copyright Year	1996
Description	Author affiliation: Dept. of Electr. & Comput. Eng., Iowa Univ., Iowa City, IA, USA (Shi, C.-J.R.)
Abstract	Via minimization is an important problem in integrated circuit layout and printed circuit board design. A linear (non-integral) programming approach to two-layer constrained via minimization (CVM) is presented. The approach finds optimum solutions for routings containing no more than three way splits, and guarantees provably good results for the general case. Most importantly, the size of linear programming formulation is polynomial in terms of the size of the CVM problem. The significance of the work lies in three aspects. First, since linear programming can be solved in polynomial time, the work thus provides, for the first time, a mathematical programming solution with computational efficiency comparable to known combinatorial CVM algorithms. Second, the compact linear programming approach is provably good and natural for general CVM, while previous restricted CVM algorithms are difficult to he extended to the general case. Third, the approach can handle additional constraints in a unified manner, and thus provides an efficient method for performance-driven layer assignment. The approach is based on some new graph-theoretic and polyhedron-combinatorial results presented on the structure of the CVM problem.
Starting Page	635
Ending Page	640
File Size	636023
Page Count	6
File Format	PDF
ISBN	0780336623
DOI	10.1109/ASPDAC.1997.600347
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1997-01-28
Publisher Place	Japan
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Linear programming Routing Wire Minimization Printed circuits Polynomials Cities and towns Integrated circuit layout Computational efficiency Transmission line theory
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A signed hypergraph model of constrained via minimization

A graph-theoretic via minimization algorithm for two-layer printed circuit boards

An Analytical Method for Compacting Routing Area in Integrated Circuits

The constrained via minimization problem for PCB and VLSI design

A Preprocessor for the Via Minimization Problem

Via Minimization by Layout Modification

HAM-a hardware accelerator for multi-layer wire routing

Performance-driven layer assignment for printed circuit boards and integrated circuits

Total Verification of Printed Circuit Artwork

Solving constrained via minimization by compact linear programming

Similar Documents

A signed hypergraph model of constrained via minimization

A graph-theoretic via minimization algorithm for two-layer printed circuit boards

An Analytical Method for Compacting Routing Area in Integrated Circuits

The constrained via minimization problem for PCB and VLSI design

A Preprocessor for the Via Minimization Problem

Via Minimization by Layout Modification

HAM-a hardware accelerator for multi-layer wire routing

Performance-driven layer assignment for printed circuit boards and integrated circuits

Total Verification of Printed Circuit Artwork

Solving constrained via minimization by compact linear programming