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)

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

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

• ``Integer-making theorems
• 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

Cited in

(17)

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

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)