Multiterminal global routing: A deterministic approximation scheme

DOI10.1007/BF01759035MaRDI QIDQ916369zbMATH OpenFDO

Authors Prabhakar Raghavan, Clark D. Thompson

Publication date 1991

Published in Algorithmica (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmglobal routing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Recommendations

• A $1.6$ Approximation Algorithm for Routing Multiterminal Nets
• scientific article; zbMATH DE number 1559579
• Integer Programming and Combinatorial Optimization
• Channel routing of multiterminal nets
• Optimal Dynamic Routing in Multidestination Networks
• scientific article; zbMATH DE number 3898776
• A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria
• Nearly optimal algorithms and bounds for multilayer channel routing
• An approximation algorithm for multiroute flow decomposition

Cites work

• A new polynomial-time algorithm for linear programming
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• Balancing families of sets
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• ``Integer-making theorems

Cited in

(16)

• A new algorithm for standard cell global routing
• A $1.6$ Approximation Algorithm for Routing Multiterminal Nets
• Probability-driven routing in a datapath environment
• Global wire routing in two-dimensional arrays
• Integer programming in VLSI design
• scientific article; zbMATH DE number 1830745 (Why is no real title available?)
• Algorithms and Computation
• Provably good global routing of integrated circuits
• A fast heuristic algorithm for the maximum concurrent \(k\)-splittable flow problem
• On Canonical Concurrent Flows, Crossing Number and Graph Expansion
• scientific article; zbMATH DE number 3898776 (Why is no real title available?)
• Randomized rounding in the presence of a cardinality constraint
• Integer Programming and Combinatorial Optimization
• Randomized metarounding
• Multiterminal net assignments by scatter search
• Maximum alignment of interchangeable terminals

This page was built for publication: Multiterminal global routing: A deterministic approximation scheme

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