Minimum Eccentricity Shortest Path Problem: An Approximation Algorithm and Relation with the k-Laminarity Problem

Abstract : The Minimum Eccentricity Shortest Path (MESP) Problem consists in determining a shortest path (a path whose length is the distance between its extremities) of minimum eccentricity in a graph. It was introduced by Dragan and Leitert [9] who described a linear-time algorithm which is an 8-approximation of the problem. In this paper, we study deeper the double-BFS procedure used in that algorithm and extend it to obtain a linear-time 3-approximation algorithm. We moreover study the link between the MESP problem and the notion of laminarity, introduced by Völkel et al [12], corresponding to its restriction to a diameter (i.e. a shortest path of maximum length), and show tight bounds between MESP and laminarity parameters.
Type de document :
Communication dans un congrès
COCOA 2016, Combinatorial Optimization and Applications - 10th International Conference, Dec 2016, Hong Kong, China. pp.216 - 229, 2016, <https://conference.cs.cityu.edu.hk/cocoa2016/>. <10.1007/978-3-319-48749-6_16>
Liste complète des métadonnées

https://hal.inria.fr/hal-01424469
Contributeur : Fabien De Montgolfier <>
Soumis le : lundi 2 janvier 2017 - 15:58:24
Dernière modification le : mercredi 4 janvier 2017 - 01:13:14
Document(s) archivé(s) le : mardi 4 avril 2017 - 00:39:14

Fichiers

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Étienne Birmelé, Fabien De Montgolfier, Léo Planche. Minimum Eccentricity Shortest Path Problem: An Approximation Algorithm and Relation with the k-Laminarity Problem. COCOA 2016, Combinatorial Optimization and Applications - 10th International Conference, Dec 2016, Hong Kong, China. pp.216 - 229, 2016, <https://conference.cs.cityu.edu.hk/cocoa2016/>. <10.1007/978-3-319-48749-6_16>. <hal-01424469>

Partager

Métriques

Consultations de
la notice

129

Téléchargements du document

23