CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Optimal Wiring on Rectangular Structure

by Pawan Kumar Patel, Rohit Kumar, Nikita Gulati
journal cover thumbnail

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

@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 },
issue_date = { November 2013 },
volume = { 82 },
number = { 14 },
month = { November },
year = { 2013 },
issn = { 0975-8887 },
pages = { 29-36 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume82/number14/14230-1675/ },
doi = { 10.5120/14230-1675 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:57:43.451893+05:30
%A Pawan Kumar Patel
%A Rohit Kumar
%A Nikita Gulati
%T Optimal Wiring on Rectangular Structure
%J International Journal of Computer Applications
%@ 0975-8887
%V 82
%N 14
%P 29-36
%D 2013
%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
  1. 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.
  2. R. M Karp. Reducibility among combinatorial problems. R. E. Miller and J. W. Thatcher, Plenum press, New York, USA, 1972.
  3. S. Aaronson. Is P versus NP formally independent? Bulletin of the European Association for Theoretical Computer Science, 81, Oct. 2003
  4. 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

Computer Science
Information Sciences

Keywords

Wiring on rectangular structure NP-hard Computational geometry Graph theory

Powered by PhDFocusTM