A Linear-Time Algorithm for the Homotopic Routing Problem in Grid Graphs

DOI10.1137/S0097539789162109zbMath0803.68057OpenAlexW2035150193MaRDI QIDQ4291553

Michael Kaufmann, Kurt Mehlhorn

Publication date: 10 May 1994

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

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

zbMATH Keywords

algorithmsedge-disjoint pathshomotopic routingVLSI-theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Related Items (2)

A generic algorithm for one-dimensional homotopic compaction ⋮ Parity conditions in homotopic knock-knee routing

This page was built for publication: A Linear-Time Algorithm for the Homotopic Routing Problem in Grid Graphs