On local routing of two-terminal nets

DOI10.1016/0095-8956(92)90031-RzbMath0810.05063OpenAlexW1990708537MaRDI QIDQ1210582

Kurt Mehlhorn, Michael Kaufmann

Publication date: 7 February 1995

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(92)90031-r

zbMATH Keywords

algorithmroutingfacesedge-disjoint pathsfinite grid graphlocal routing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

APPROXIMATE SHORTEST HOMOTOPIC PATHS IN WEIGHTED REGIONS ⋮ Parity conditions in homotopic knock-knee routing

Cites Work

• Disjoint paths in a rectilinear grid
• Algorithms for routing in planar graphs
• Edge-disjoint homotopic paths in a planar graph with one hole
• Multicommodity flows in planar graphs
• Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
• Routing through a generalized switchbox