A 1.6 Approximation Algorithm for Routing Multiterminal Nets

DOI10.1137/0216046MaRDI QIDQ3801063zbMATH OpenOpenAlexFDO

Authors Sing-Ling Lee, Teofilo F. Gonzalez

Publication date 1987

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0216046

zbMATH Keywords

VLSIgreedy methodswire routingminimal chip arearouting around one module

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Recommendations

• Multiterminal global routing: A deterministic approximation scheme
• An improved approximation algorithm for capacitated multicast routings in networks
• An approximation algorithm for multiroute flow decomposition
• An approximation algorithm for the general routing problem
• An improved approximation algorithm for multicast \(k\)-tree routing
• Routing multiterminal nets on a hexagonal grid
• Approximation algorithms for multicast routing in ad hoc wireless networks
• Nearly optimal algorithms and bounds for multilayer channel routing
• Computing and Combinatorics
• Approximating capacitated tree-routings in networks

Cited in

(6)

• Grid stretching algorithms for routing multiterminal nets through a rectangle
• Improved approximation algorithms for embedding hyperedges in a cycle
• Routing Multiterminal Nets Around a Rectangle
• An efficient one-side height minimization algorithm for routing around a rectangle
• Multiterminal net assignments by scatter search
• Multiterminal global routing: A deterministic approximation scheme

This page was built for publication: A $1.6$ Approximation Algorithm for Routing Multiterminal Nets

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