Name
Abstract | ||
|---|---|---|
The d-Dimh-hops MST problem is defined as follows: given a set S of points in the d-dimensional Euclidean space and sεS, find a minimum-cost spanning tree for S rooted at s with height at most h. We investigate the problem for any constant h and d 0. We prove the first nontrivial lower bound on the solution cost for almost all Euclidean instances (i.e. the lower bound holds with high probability). Then we introduce an easy-to-implement, fast divide et impera heuristic and we prove that its solution cost matches the lower bound. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.tcs.2007.04.039 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
random Euclidean instance,bounded height minimum spanning tree,Bounded height minimum spanning tree,solution cost,high probability,Randomized algorithms,Approximation algorithms,d-dimensional Euclidean space,approximation algorithms,constant h,d-Dimh-hops MST problem,randomized algorithms,bounded-hop MST problem,Euclidean instance | Journal | 384 |
Issue | ISSN | Citations |
2-3 | Theoretical Computer Science | 2 |
PageRank | References | Authors |
0.38 | 17 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrea E. F. Clementi | 1 | 1168 | 85.30 |
| Miriam di Ianni | 2 | 144 | 17.27 |
| Massimo Lauria | 3 | 122 | 14.73 |
| Angelo Monti | 4 | 671 | 46.93 |
| Gianluca Rossi | 5 | 235 | 21.60 |
| Riccardo Silvestri | 6 | 1324 | 90.84 |