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

DOI10.1137/S0097539789162109MaRDI QIDQ4291553zbMATH OpenOpenAlexFDO

Authors Michael Kaufmann, K. 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)

Recommendations

• scientific article; zbMATH DE number 4211829
• On local routing of two-terminal nets
• Edge-disjoint paths in a grid bounded by two nested rectangles
• scientific article; zbMATH DE number 4031743
• scientific article; zbMATH DE number 4083048

Cited in

(8)

• Routing and timetabling by topological search
• Parity conditions in homotopic knock-knee routing
• Escaping a grid by edge-disjoint paths
• scientific article; zbMATH DE number 5863215 (Why is no real title available?)
• scientific article; zbMATH DE number 4211829 (Why is no real title available?)
• Homotopic Rectilinear Routing with Few Links and Thick Edges
• Spanning closed trail and hamiltonian cycle in grid graphs
• A generic algorithm for one-dimensional homotopic compaction

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

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