Bulletin of the European Association for Theoretical Computer Science · 2017 · 22 citations · 0 references
EngineeringComputer ScienceElectrical EngineeringMicroelectronicsSemiconductor DevicesVlsi DesignCombinatorial OptimizationIntegrated Circuit DesignVery-large-scale Integration LayoutVery-large-scale IntegrationVery-large-scale Integration (Vlsi) DesignVlsi Implementation
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.