The MST of Symmetric Disk Graphs (in Arbitrary Metrics) is Light

Details The MST of Symmetric Disk Graphs (in Arbitrary Metrics) is Light The MST of Symmetric Disk Graphs (in Arbitrary Metrics) is Light

2011-02-23

arxiv.org/abs/1102.4866v1

Computer Science

Computational Geometry

13 pages, 1 figure

Scientific paper

Consider an n-point metric M = (V,delta), and a transmission range assignment r: V \rightarrow \mathbb R^+ that maps each point v in V to the disk of radius r(v) around it. The {symmetric disk graph} (henceforth, SDG) that corresponds to M and r is the undirected graph over V whose edge set includes an edge (u,v) if both r(u) and r(v) are no smaller than delta(u,v). SDGs are often used to model wireless communication networks. Abu-Affash, Aschner, Carmi and Katz (SWAT 2010, \cite{AACK10}) showed that for any {2-dimensional Euclidean} n-point metric M, the weight of the MST of every {connected} SDG for M is O(log n) w(MST(M)), and that this bound is tight. However, the upper bound proof of \cite{AACK10} relies heavily on basic geometric properties of 2-dimensional Euclidean metrics, and does not extend to higher dimensions. A natural question that arises is whether this surprising upper bound of \cite{AACK10} can be generalized for wider families of metrics, such as 3-dimensional Euclidean metrics. In this paper we generalize the upper bound of Abu-Affash et al. \cite{AACK10} for Euclidean metrics of any dimension. Furthermore, our upper bound extends to {arbitrary metrics} and, in particular, it applies to any of the normed spaces ell_p. Specifically, we demonstrate that for {any} n-point metric M, the weight of the MST of every connected SDG for M is O(log n) w(MST(M)).

Affiliated with

Also associated with

No associations

Rating

The MST of Symmetric Disk Graphs (in Arbitrary Metrics) is Light does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The MST of Symmetric Disk Graphs (in Arbitrary Metrics) is Light, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The MST of Symmetric Disk Graphs (in Arbitrary Metrics) is Light will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-85901