Research Article
Approximation Algorithm for Optimal Wiring on Rectangular Structure
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 75 - Issue 14 |
| Published: August 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 },
year = { 2013 },
volume = { 75 },
number = { 14 },
pages = { 1-4 },
doi = { 10.5120/13176-0675 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2013
%A Pawan Kumar Patel
%A Manoj Diwakar
%A Kunal Gupta
%A Amrendra Tripathi
%T Approximation Algorithm for Optimal Wiring on Rectangular Structure%T
%J International Journal of Computer Applications
%V 75
%N 14
%P 1-4
%R 10.5120/13176-0675
%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
- 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.
- Michel X. Goemans and David P. Williamson. A general approximation technique for constrained forest problems. Siam J. Comput. . , 24(2): 296-317, 1995.
- 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.
- 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
- 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.
- D. Eppstein. Faster geometric k-point mst approximation. Technical Report 13, University of Califomia, Imine, CA, 1995.
- 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.
- M. Goemans and D. Williamson. A general approximation technique for constrained forest problems. SIAM J. Comput. , 24~296-3 17,1995.
- 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.
- 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
Keywords