Symmetric range assignment with disjoint MST constraints

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Symmetric range assignment with disjoint MST constraints

Full text

Pdf (171 KB)

Source

Workshop on Discrete Algothrithms and Methods for MOBILE Computing and Communications archive
Proceedings of the fifth international workshop on Foundations of mobile computing table of contents

Toronto, Canada

SESSION: Wireless networks II (topology control) table of contents

Pages 65-70

Year of Publication: 2008

ISBN:978-1-60558-244-3

Author

Eric Schmutz

Drexel University, Philadelphia, PA, USA

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 19, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1400863.1400877 What is a DOI?

ABSTRACT

If V is a set of n points in the unit square [0,1]², and if R:V-> Re₊ is an assignment of positive real numbers (radii) to to those points, define a graph G(R) as follows: [v,w] is an undirected edge if and only if the Euclidean distance d(v,w) is less than or equal to min(R(v),R(w)). Given α≥ 1 and k∈ Z₊, let R_k* be the range assignment that minimizes the function J(R) =sum limits_{v #8712; V}R(v)^α, subject to the constraint that G(R) has at least k edge-disjoint spanning trees. For n random points in [0,1]², the expected value of the optimum, E(J(R_k*)), is asymptotically Θ(n^1-α/2). This is proved by analyzing a crude approximation algorithm that finds a range assignment R_k^a such that the ratio J(R_k^a)/J(R_k*) is bounded.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	D. Aldous and J. M. Steele. Asymptotics for Euclidean minimal spanning trees on random points. Probab. Theory Related Fields, 92(2):247--258, 1992.
	2	E. Althaus , G. Calinescu , I. I. Mandoiu , S. Prasad , N. Tchervenski , A. Zelikovsky, Power efficient range assignment for symmetric connectivity in static ad hoc wireless networks, Wireless Networks, v.12 n.3, p.287-299, May 2006 [doi>10.1007/s11276-005-5275-x]
	3	F. Avram and D. Bertsimas. The minimum spanning tree constant in geometrical probability and under the independent model: a unified approach. Ann. Appl. Probab., 2(1):113--130, 1992.
	4	Douglas M. Blough , Mauro Leoncini , Giovanni Resta , Paolo Santi, On the Symmetric Range Assignment Problem in Wireless Ad Hoc Networks, Proceedings of the IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science: Foundations of Information Technology in the Era of Networking and Mobile Computing, p.71-82, August 25-30, 2002
	5	Gruia Calinescu , Peng-jun Wan, Range assignment for biconnectivity and k-edge connectivity in wireless ad hoc networks, Mobile Networks and Applications, v.11 n.2, p.121-128, April 2006 [doi>10.1007/s11036-006-4466-8]
	6	J. Clausen and L. A. Hansen. Finding k edge-disjoint spanning trees of minimum total weight in a network: an application of matroid theory. Math. Programming Stud., (13):88--101, 1980. Combinatorial optimization, II (Proc. Conf., Univ. East Anglia, Norwich, 1979).
	7	Andrea E. F. Clementi , Paolo Penna , Riccardo Silvestri, On the power assignment problem in radio networks, Mobile Networks and Applications, v.9 n.2, p.125-140, April 2004 [doi>10.1023/B:MONE.0000013624.32948.87]
	8	Bernhard Fuchs, On the hardness of range assignment problems, Networks, v.52 n.4, p.183-195, December 2008 [doi>10.1002/net.v52:4]
	9	D. Gusfield. Connectivity and edge-disjoint spanning trees. Inform. Process. Lett., 16(2):87--89, 1983.
	10	MohammadTaghi Hajiaghayi , Nicole Immorlica , Vahab S. Mirrokni, Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939016]
	11	H. Kesten and S. Lee. The central limit theorem for weighted minimal spanning trees on random points. Ann. Appl. Probab., 6(2):495--527, 1996.
	12	G. Kortsarz, V. S. Mirrokni, Z. Nutov, and E. Tsanko. Approximating minimum-power degree and connectivity problems. In LATIN, pages 423--435, 2008.
	13	Errol L. Lloyd , Rui Liu , Madhav V. Marathe , Ram Ramanathan , S. S. Ravi, Algorithmic aspects of topology control problems for ad hoc networks, Mobile Networks and Applications, v.10 n.1-2, p.19-34, February 2005 [doi>10.1145/1046430.1046433]
	14	Clyde Monma , Subhash Suri, Transitions in geometric minimum spanning trees, Discrete & Computational Geometry, v.8 n.3, p.265-293, 1992 [doi>10.1007/BF02293049]
	15	M. D. Penrose. The longest edge of the random minimal spanning tree. Ann. Appl. Probab., 7(2):340--361, 1997.
	16	J. Roskind and R. E. Tarjan. A note on finding minimum-cost edge-disjoint spanning trees. Math. Oper. Res., 10(4):701--708, 1985.
	17	J. M. Steele. Probability theory and combinatorial optimization, volume 69 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997.