Minimum Eccentricity Shortest Path Problem: An Approximation Algorithm and Relation with the k-Laminarity Problem - Archive ouverte HAL Access content directly
Conference Papers Year : 2016

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

(1) , (2, 3) , (1, 3)
1
2
3

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.
Fichier principal
Vignette du fichier
main.pdf (194.44 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01424469 , version 1 (02-01-2017)

Identifiers

Cite

Etienne E. 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, ⟨10.1007/978-3-319-48749-6_16⟩. ⟨hal-01424469⟩
212 View
348 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More