The d-Dim h-HOPS MST problem is defined as follows: given a set S of points in the d-dimensional Euclidean space and S E 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. (C) 2007 Elsevier B.V. All rights reserved.
On the bounded-hop MST problem on random Euclidean instances / Andrea E. F., Clementi; Miriam Di, Ianni; Lauria, Massimo; Monti, Angelo; Gianluca, Rossi; Silvestri, Riccardo. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 384:2-3(2007), pp. 161-167. (Intervento presentato al convegno 12th International Colloquium on Structural Information and Communication Complexity tenutosi a Mont St Michel, FRANCE nel MAY 24-26, 2005) [10.1016/j.tcs.2007.04.039].
On the bounded-hop MST problem on random Euclidean instances
LAURIA, MASSIMO;MONTI, Angelo;SILVESTRI, RICCARDO
2007
Abstract
The d-Dim h-HOPS MST problem is defined as follows: given a set S of points in the d-dimensional Euclidean space and S E 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. (C) 2007 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
