Optimal Wiring on Rectangular Structure
Pawan KumarPatel, Rohit Kumar, Nikita Gulati · International Journal of Computer Applications · 2013
In this paper we worked upon on optimal wiring on rectangular structure.Here we are given a rectangle partitioned into smaller rectangles by axis-parallel line segments.Find a subset of the segments such that the resulting structure from these segments is connected and it touches every smaller rectangle.Here we reduce the problem of exact cover by 3-sets (X3C), which is known to be NP-complete, into this problem and thus claim wiring problem to be NP-hard.This problem carries a special importance because very few problems in the domain of geometry are known to be NP-hard.