The week's pick
Random Articles
Reseach Article
Optimal Wiring on Rectangular Structure
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 82 - Number 14 |
| Year of Publication: 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
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