Multiterminal global routing: A deterministic approximation scheme

DOI10.1007/BF01759035zbMath0703.68048MaRDI QIDQ916369

Clark D. Thompson, Prabhakar Raghavan

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)

Related Items (5)

Randomized metarounding ⋮ A fast heuristic algorithm for the maximum concurrent \(k\)-splittable flow problem ⋮ On Canonical Concurrent Flows, Crossing Number and Graph Expansion ⋮ Integer programming in VLSI design ⋮ Randomized Rounding in the Presence of a Cardinality Constraint

Cites Work

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

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