A decomposition algorithm for circuit routing

DOI10.1007/BFB0121044MaRDI QIDQ3710289zbMATH OpenOpenAlexFDO

Authors

Publication date 1985

Published in Mathematical Programming Essays in Honor of George B. Dantzig Part I (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bfb0121044

zbMATH Keywords

Circuit routingcut paste approachdecomposition principleinteger linear programlarge linear program

Mathematics Subject Classification ID

Decomposition methods (49M27) Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Integer programming (90C10)

Recommendations

• An approximation algorithm for multiroute flow decomposition
• Decomposition algorithms for finding the shortest path between a source node and a sink node of a network
• An optimal distributed routing algorithm using dual decomposition techniques
• A decomposition algorithm for multi-terminal network flows
• scientific article; zbMATH DE number 3860397
• scientific article; zbMATH DE number 4106903
• An axiomatic approach to routing
• Algorithms – ESA 2005
• Dynamic programming in the routing problem: decomposition variant
• A new proximal decomposition algorithm for routing in telecommunication networks

Cited in

(5)

• Global wire routing in two-dimensional arrays
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Integer programming in VLSI design
• The pin redistribution problem in multi-chip modules

This page was built for publication: A decomposition algorithm for circuit routing

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