Name
Abstract | ||
|---|---|---|
Given a one-dimensional graph G 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 G) is O(log n), we prove an Ω(n log n/log log n) lower bound on the sum of lengths of all the edges (i.e., the weight of G). 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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.5555/1070432.1070525 | SODA |
Keywords | Field | DocType |
partial sum problem,log log n,one-dimensional graph,small diameter,sparse euclidean spanner,consecutive node,n log n,minimum number,log n,euclidean spanner graph,low weight,greedy algorithm,partial sums,lower bound,upper bound | Log-log plot,Discrete mathematics,Binary logarithm,Combinatorics,Bound graph,Upper and lower bounds,Greedy algorithm,Euclidean geometry,Spanner,Time complexity,Mathematics | Conference |
ISBN | Citations | PageRank |
0-89871-585-7 | 9 | 0.43 |
References | Authors | |
4 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pankaj K. Agarwal | 1 | 5257 | 593.81 |
| Yusu Wang | 2 | 15 | 0.96 |
| Peng Yin | 3 | 25 | 2.74 |