A linear time algorithm for optimal routing around a rectangle

DOI10.1145/48014.48018MaRDI QIDQ3816979zbMATH OpenOpenAlexFDO

Authors Sing-Ling Lee, Teofilo F. Gonzalez

Publication date 1988

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/48014.48018

zbMATH Keywords

routingVLSI layout

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99) Circuits, networks (94C99)

Recommendations

• Algorithms for routing around a rectangle
• OPTIMAL ROUTING THROUGH DENSE CHANNELS
• A Provably Good Algorithm for the Two Module Routing Problem
• Routing Multiterminal Nets Around a Rectangle
• Routing in polygons without rectilinearly visible corners

Cited in

(8)

• On minimizing the maximum congestion for weighted hypergraph embedding in a cycle
• An efficient one-side height minimization algorithm for routing around a rectangle
• Algorithms for routing around a rectangle
• Improved approximation algorithms for embedding hyperedges in a cycle
• scientific article; zbMATH DE number 3959289 (Why is no real title available?)
• A Provably Good Algorithm for the Two Module Routing Problem
• Time complexity of a path formulated optimal routing algorithm (second printing)
• Optimal algorithms for adjacent side routing

This page was built for publication: A linear time algorithm for optimal routing around a rectangle

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