Via Minimization with Pin Preassignments and Layer Preference

DOI10.1002/ZAMM.19890691107MaRDI QIDQ3197850zbMATH OpenOpenAlexFDO

Authors Martin Grötschel, Michael Jünger, Gerhard Reinelt

Publication date 1989

Published in ZAMM - Journal of Applied Mathematics and Mechanics / Zeitschrift für Angewandte Mathematik und Mechanik (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/zamm.19890691107

zbMATH Keywords

algorithmslayer preferencesmax-cut problempin preassignmentsprinted circuit board designVLSI

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35) Applications of graph theory to circuits and networks (94C15)

Recommendations

• scientific article; zbMATH DE number 1058028
• Constrained via minimization for three-layer routing
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• scientific article; zbMATH DE number 3985121
• An algorithm for the via assignment problem in multilayer backboard wiring

Cites work

• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• An Efficient Heuristic Procedure for Partitioning Graphs

Cited in

(18)

• Constrained via minimization for three-layer routing
• An integrated approach to routing and via minimization
• The pin redistribution problem in multi-chip modules
• Steiner tree packing revisited
• On the diameter of cut polytopes
• A hierarchy preserving hierarchical bottom-up 2-layer wiring algorithm with respect to via minimization
• scientific article; zbMATH DE number 3985121 (Why is no real title available?)
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• An algorithm for the via assignment problem in multilayer backboard wiring
• Solving VLSI design and DNA sequencing problems using bipartization of graphs
• Partitioning planar graphs: a fast combinatorial approach for max-cut
• scientific article; zbMATH DE number 1058028 (Why is no real title available?)
• Optimal control of plotting and drilling machines: A case study
• From equipartition to uniform cut polytopes: extended polyhedral results
• A polynomial-time recursive algorithm for some unconstrained quadratic optimization problems
• Conjugate conflict continuation graphs for multi-layer constrained via minimization
• Mathematical methods for physical layout of printed circuit boards: an overview
• Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems

This page was built for publication: Via Minimization with Pin Preassignments and Layer Preference

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3197850)