Loading...
Please wait, while we are loading the content...
Similar Documents
Lower bound for sparse euclidean spanners (2005)
| Content Provider | CiteSeerX |
|---|---|
| Author | Agarwal, Pankaj K. |
| Description | Given a one-dimensional graph ¢ such that any two consecutive nodes are unit distance away, and such that the minimum number of links between any two nodes (the diameter of ¢ ) is £¥¤§¦©¨����� � , we prove an ��¤§��¦�¨�������¦�¨���¦©¨����� � lower bound on the sum of lengths of all the edges (i.e., the weight of ¢). The problem is a variant of the widely studied partial sum problem. This in turn provides a lower bound on Euclidean spanner graphs with small diameter and low weight, showing that the upper bound from [1] is almost tight. 1 |
| File Format | |
| Language | English |
| Publisher Date | 2005-01-01 |
| Publisher Institution | in Proc. of ACM Symp. on Discrete Algorithms (SODA |
| Access Restriction | Open |
| Subject Keyword | Partial Sum Problem Low Weight Euclidean Spanner Graph Upper Bound One-dimensional Graph Unit Distance Consecutive Node Small Diameter Minimum Number Sparse Euclidean Spanner |
| Content Type | Text |
| Resource Type | Article |
