Approximation Algorithm for Optimal Wiring on Rectangular Structure
Pawan KumarPatel, Manoj Diwakar, Kunal Gupta, Amrendra Tripathi · International Journal of Computer Applications · 2013
In this paper we discuss our attempts to find an approximation for the optimal wiring on rectangular structure.Here we are given a rectangle partitioned into smaller rectangles by axisparallel line segments.Find a subset of the segments such that the resulting structure from these segments is connected and it touches every smaller rectangles.Although these attempts have not yielded any satisfactory result but gives direction to solve this problem need a very different approach.