Research Article
Optimal Wiring on Rectangular Structure
|
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 |
10.5120/14230-1675
|
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
Abstract
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.
References
- M. R. Garey, R. L. Graham, and D. s. Johnson. Some np-complete geometric problems. In STOC 76 : Proceeding of the eighth annual ACM symposium on theory of computing, page 10-22, New York, NY, USA, 1976. ACM Press.
- R. M Karp. Reducibility among combinatorial problems. R. E. Miller and J. W. Thatcher, Plenum press, New York, USA, 1972.
- S. Aaronson. Is P versus NP formally independent? Bulletin of the European Association for Theoretical Computer Science, 81, Oct. 2003
- R. Impagliazzo, R. Paturi, and F. Zane, Which Problems Have Strongly Exponential Complexity?, Journal of Computer and System Sciences 63-4, (2001), pp. 512-530.
Index Terms
Keywords