Parity conditions in homotopic knock-knee routing

DOI10.1007/BF01185338zbMath0760.68034OpenAlexW2079826661MaRDI QIDQ1207328

Michael Kaufmann, F. Miller Maley

Publication date: 1 April 1993

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01185338

zbMATH Keywords

homotopic routingevenness conditionknock-knee model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

A generic algorithm for one-dimensional homotopic compaction

Cites Work

• Unnamed Item
• Decomposition of graphs on surfaces and a homotopic circulation theorem
• A generic algorithm for one-dimensional homotopic compaction
• Disjoint paths in a rectilinear grid
• Algorithms for routing in planar graphs
• Multicommodity flows in planar graphs
• On local routing of two-terminal nets
• Edge-Disjoint Homotopic Paths in Straight-Line Planar Graphs
• Optimal Three-Layer Channel Routing
• Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
• Routing through a generalized switchbox
• A Linear-Time Algorithm for the Homotopic Routing Problem in Grid Graphs

This page was built for publication: Parity conditions in homotopic knock-knee routing