Name
Title | ||
|---|---|---|
An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks |
Abstract | ||
|---|---|---|
Computing energy efficient broadcast trees is one of the most prominent operations in wireless networks. For stations embedded in the Euclidean plane, the best analytic result known to date is a 6.33-approximation algorithm based on computing an Euclidean minimum spanning tree. We improve the analysis of this algorithm and show that its approximation ratio is 6, which matches a previously known lower bound for this algorithm. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11523468_92 | international colloquium on automata, languages and programming |
Keywords | Field | DocType |
efficient broadcast tree,approximation ratio,wireless network,energy efficient broadcast tree,mst algorithm,euclidean plane,euclidean minimum,analytic result,prominent operation,computing energy | Broadcasting,Wireless network,Efficient energy use,Upper and lower bounds,Algorithm,Euclidean minimum spanning tree,Euclidean geometry,Mathematics | Conference |
Volume | ISSN | ISBN |
3580 | 0302-9743 | 3-540-27580-0 |
Citations | PageRank | References |
41 | 1.50 | 14 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Ambühl | 1 | 357 | 18.50 |