Algorithms for routing around a rectangle

DOI10.1016/0166-218X(92)90007-WMaRDI QIDQ1208452zbMATH OpenFDO

Authors Takao Nishizeki, Nobuji Saito, Hitoshi Suzuki, Éva Tardos, András Frank

Publication date 16 May 1993

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(92)90007-W

zbMATH Keywords

routing problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A linear time algorithm for optimal routing around a rectangle
• An efficient one-side height minimization algorithm for routing around a rectangle
• Algorithms for routing in planar graphs
• Routing Multiterminal Nets Around a Rectangle
• Routing in polygons without rectilinearly visible corners
• Routing among convex polygonal obstacles in the plane
• Routing in polygonal domains
• Routing in polygonal domains
• Algorithms for generalized round robin routing
• Algorithms for Rectangular Covering Problems

Cites work

• A linear time algorithm for optimal routing around a rectangle
• Edge-disjoint paths in planar graphs
• scientific article; zbMATH DE number 3214398 (Why is no real title available?)
• Multicommodity flows in planar graphs
• Variable-priority queue and doughnut routing

Cited in

(23)

• Routing to reduce the cost of wavelength conversion
• On minimizing the maximum congestion for weighted hypergraph embedding in a cycle
• A polynomial time approximation scheme for embedding a directed hypergraph on a ring
• An efficient one-side height minimization algorithm for routing around a rectangle
• Routing in polygons without rectilinearly visible corners
• Sonet ring sizing with genetic algorithms
• Exact solution of the SONET ring loading problem
• On packing and coloring hyperedges in a cycle
• Multicommodity flows in cycle graphs
• A note on the ring loading problem
• Improved approximation algorithms for embedding hyperedges in a cycle
• Optimal online ring routing
• scientific article; zbMATH DE number 3932954 (Why is no real title available?)
• Routing Multiterminal Nets Around a Rectangle
• Routing through a generalized switchbox
• A linear time algorithm for optimal routing around a rectangle
• Grid stretching algorithms for routing multiterminal nets through a rectangle
• scientific article; zbMATH DE number 1234989 (Why is no real title available?)
• A polynomial time approximation scheme for embedding hypergraph in a weighted cycle
• Optimal algorithms for adjacent side routing
• The weighted link ring loading problem
• Integral polyhedra related to integer multicommodity flows on a cycle
• A polynomial-time algorithm for the weighted link ring loading problem with integer demand splitting

This page was built for publication: Algorithms for routing around a rectangle

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