On the rectilinear Steiner problem

Andreas Blass, Yuri Gurevich, The Logic in Computer Science Column by Yuri Gurevich


This is a gentle introduction to the Rectilinear Steiner Problem. The
interest in the Rectilinear Steiner Problem is related to the Very Large-Scale
Integration (VLSI) technology that combines thousands of transistors into a
single chip. Our note is based on the pioneering paper of Maurice Hanan.
The main result of Hanan is an algorithm reducing any solution to a solution
within a so-called Hanan grid. We simplify Hanan’s algorithm.

Full Text:



  • There are currently no refbacks.