International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
Volume 82 - Issue 14 |
Published: November 2013 |
Authors: Pawan Kumar Patel, Rohit Kumar, Nikita Gulati |
![]() |
Pawan Kumar Patel, Rohit Kumar, Nikita Gulati . Optimal Wiring on Rectangular Structure. International Journal of Computer Applications. 82, 14 (November 2013), 29-36. DOI=10.5120/14230-1675
@article{ 10.5120/14230-1675, author = { Pawan Kumar Patel,Rohit Kumar,Nikita Gulati }, title = { Optimal Wiring on Rectangular Structure }, journal = { International Journal of Computer Applications }, year = { 2013 }, volume = { 82 }, number = { 14 }, pages = { 29-36 }, doi = { 10.5120/14230-1675 }, publisher = { Foundation of Computer Science (FCS), NY, USA } }
%0 Journal Article %D 2013 %A Pawan Kumar Patel %A Rohit Kumar %A Nikita Gulati %T Optimal Wiring on Rectangular Structure%T %J International Journal of Computer Applications %V 82 %N 14 %P 29-36 %R 10.5120/14230-1675 %I Foundation of Computer Science (FCS), NY, USA
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.