Minimum Eccentricity Shortest Path Problem: an Approximation Algorithm and Relation with the k-Laminarity Problem
| Autor: | Fabien de Montgolfier, Léo Planche, Etienne Birmelé |
|---|---|
| Přispěvatelé: | Mathématiques Appliquées Paris 5 (MAP5 - UMR 8145), Université Paris Descartes - Paris 5 (UPD5)-Institut National des Sciences Mathématiques et de leurs Interactions (INSMI)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), MAC2 (Idex USPC), MAC2, Networks, Graphs and Algorithms (GANG), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Mathématiques Appliquées à Paris 5 ( MAP5 - UMR 8145 ), Université Paris Descartes - Paris 5 ( UPD5 ) -Institut National des Sciences Mathématiques et de leurs Interactions-Centre National de la Recherche Scientifique ( CNRS ), Institut de Recherche en Informatique Fondamentale ( IRIF ), Université Paris Diderot - Paris 7 ( UPD7 ) -Centre National de la Recherche Scientifique ( CNRS ), Networks, Graphs and Algorithms ( GANG ), Université Paris Diderot - Paris 7 ( UPD7 ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Paris Diderot - Paris 7 ( UPD7 ) -Centre National de la Recherche Scientifique ( CNRS ) -Inria de Paris, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) |
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
FOS: Computer and information sciences
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] k-Laminar Graph BFS Discrete Mathematics (cs.DM) [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] 0102 computer and information sciences 02 engineering and technology Computational Complexity (cs.CC) [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Graph search 01 natural sciences Eccentricity Combinatorics Diameter 0202 electrical engineering electronic engineering information engineering Yen's algorithm [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS] Mathematics Discrete mathematics [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM] Longest path problem Widest path problem Graph theory Computer Science - Computational Complexity Euclidean shortest path [ INFO.INFO-CC ] Computer Science [cs]/Computational Complexity [cs.CC] Shortest Path Faster Algorithm 010201 computation theory & mathematics Shortest path problem 020201 artificial intelligence & image processing K shortest path routing Approximation Algorithms Distance Computer Science - Discrete Mathematics |
| Zdroj: | COCOA 2016, Combinatorial Optimization and Applications-10th International Conference 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⟩ MAP5 2016-26. 2016 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〉 Combinatorial Optimization and Applications ISBN: 9783319487489 COCOA |
| DOI: | 10.1007/978-3-319-48749-6_16⟩ |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|