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

Approximation Algorithm for Optimal Wiring on Rectangular Structure

by Pawan Kumar Patel, Manoj Diwakar, Kunal Gupta, Amrendra Tripathi
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 75 - Number 14
Year of Publication: 2013
Authors: Pawan Kumar Patel, Manoj Diwakar, Kunal Gupta, Amrendra Tripathi
10.5120/13176-0675

Pawan Kumar Patel, Manoj Diwakar, Kunal Gupta, Amrendra Tripathi . Approximation Algorithm for Optimal Wiring on Rectangular Structure. International Journal of Computer Applications. 75, 14 ( August 2013), 1-4. DOI=10.5120/13176-0675

@article{ 10.5120/13176-0675,
author = { Pawan Kumar Patel, Manoj Diwakar, Kunal Gupta, Amrendra Tripathi },
title = { Approximation Algorithm for Optimal Wiring on Rectangular Structure },
journal = { International Journal of Computer Applications },
issue_date = { August 2013 },
volume = { 75 },
number = { 14 },
month = { August },
year = { 2013 },
issn = { 0975-8887 },
pages = { 1-4 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume75/number14/13176-0675/ },
doi = { 10.5120/13176-0675 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:44:43.161525+05:30
%A Pawan Kumar Patel
%A Manoj Diwakar
%A Kunal Gupta
%A Amrendra Tripathi
%T Approximation Algorithm for Optimal Wiring on Rectangular Structure
%J International Journal of Computer Applications
%@ 0975-8887
%V 75
%N 14
%P 1-4
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In this paper we discuss our attempts to find an approximation for the 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 rectangles. Although these attempts have not yielded any satisfactory result but gives direction to solve this problem need a very different approach.

References
  1. Gabrial Robins and Alexander Zelikovsky. Improved steiner tree approximation in graphs. In SODA 00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, pages 770-779, Philadelphia, PA, USA, 2000. Society for Industrial and Applied Mathematics.
  2. Michel X. Goemans and David P. Williamson. A general approximation technique for constrained forest problems. Siam J. Comput. . , 24(2): 296-317, 1995.
  3. Avrim Blum, R. Ravi, and Santosh Vempala. A constant factor approximation algorithm for the k mst problem (extende abstract). In STOC 96 : Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 442-448, New York, NY, USA, 1996. ACM Press.
  4. N. Garg. A 3-approximation for the minimum tree spanning k vertices. In FOCS 96: Proceedings of the 37thannual symposium on Foundation of computer Science,Page 302, Washington, DC, USA, 1996, IEEE computer Society
  5. A. Blum, R. Ravi, and S. Vempala. A constant factor ap- proximation for the k-mst problem. In Proceedings, ACM Symposium on Theory of Computing, 1996.
  6. D. Eppstein. Faster geometric k-point mst approximation. Technical Report 13, University of Califomia, Imine, CA, 1995.
  7. N. Garg and D. Hochbaum. An O(1og k) approximation algorithm for the k minimum spanning tree problem in the plane. In Proceedings, ACM Symposium on Theory of Com- puting, 1994.
  8. M. Goemans and D. Williamson. A general approximation technique for constrained forest problems. SIAM J. Comput. , 24~296-3 17,1995.
  9. J. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: a simple new method for the geometric k-mst problem. In Proceedings, ACM-SIAM Symposium on Dis- crete Algorithms, pages 402408,1996.
  10. R. Ravi, R. Sundaram, M. Marathe, D. Rosenkrantz, and S. Ravi. Spanning trees short and small. In Proceedings, ACM-SIAM Symposium on Discrete Algorithms, 1993.
Index Terms

Computer Science
Information Sciences

Keywords

Graph theory Approximation algorithm Steiner tree wiring on rectangular structure.

Powered by PhDFocusTM