Kinetic Maintenance of Mobile k-Centres in Trees

Christophe Paul 1, 2 Stéphane Durocher 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Given a set P of points (clients) on a weighted tree T , a k-centre of P corresponds to a set of k points (facilities) on T such that the maximum graph distance between any client and its nearest facility is minimized. We consider the mobile k-centre problem on trees. Let C denote a set of n mobile clients, each of which follows a continuous tra jectory on a weighted tree T . We establish tight bounds on the maximum relative velocity of the 1-centre and 2-centre of C . When each client in C moves with linear motion along a path on T , the motions of the corresponding 1-centre and 2-centre are piecewise linear; we derive a tight combinatorial bound of Θ(n) on the complexity of the motion of the 1-centre and corresponding bounds of O(n^2 α(n)) and Ω(n^2 ) for a 2-centre, where α(n) denotes the inverse Ackermann function. We describe efficient algorithms for calculating the tra jectories of the 1-centre and 2-centre of C : the 1-centre can be found in optimal time O(n log n) and a 2-centre can be found in time O(n^2 log n). These algorithms lend themselves to implementation within the framework of kinetic data structures. Finally, we examine properties of the mobile 1-centre on graphs and describe an optimal unit-velocity 2-approximation.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2009, 157 (7), pp.1432-1446. 〈10.1007/978-3-540-77120-3_31〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00371207
Contributeur : Christophe Paul <>
Soumis le : jeudi 26 mars 2009 - 21:49:37
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Lien texte intégral

Identifiants

Collections

Citation

Christophe Paul, Stéphane Durocher. Kinetic Maintenance of Mobile k-Centres in Trees. Discrete Applied Mathematics, Elsevier, 2009, 157 (7), pp.1432-1446. 〈10.1007/978-3-540-77120-3_31〉. 〈lirmm-00371207〉

Partager

Métriques

Consultations de la notice

103