Top

Published in:

2016 | OriginalPaper | Chapter

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

Authors : Étienne Birmelé, Fabien de Montgolfier, Léo Planche

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter An Introduction to Coding Sequences of Graphs

next chapter On the Complexity of Extracting Subtree with Keeping Distinguishability

Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28(4), 1167–1181 (1999). http://dx.doi.org/10.1137/S0097539796303421 MathSciNetCrossRefMATH

Bacsó, G., Tuza, Z., Voigt, M.: Characterization of graphs dominated by induced paths. Discret. Math. 307(7–8), 822–826 (2007). http://dx.doi.org/10.1016/j.disc.2005.11.035 MathSciNetCrossRefMATH

Corneil, D.G., Dragan, F.F., Köhler, E.: On the power of BFS to determine a graph’s diameter. Networks 42(4), 209–222 (2003). http://dx.doi.org/10.1002/net.10098 MathSciNetCrossRefMATH

Corneil, D.G., Olariu, S., Stewart, L.: A linear time algorithm to compute a dominating path in an at-free graph. Inf. Process. Lett. 54(5), 253–257 (1995). http://dx.doi.org/10.1016/0020-0190(95)00021-4 MathSciNetCrossRefMATH

Corneil, D.G., Olariu, S., Stewart, L.: Asteroidal triple-free graphs. SIAM J. Discret. Math. 10(3), 399–430 (1997). http://dx.doi.org/10.1137/S0895480193250125 MathSciNetCrossRefMATH

Corneil, D.G., Olariu, S., Stewart, L.: Linear time algorithms for dominating pairs in asteroidal triple-free graphs. SIAM J. Comput. 28(4), 1284–1297 (1999). http://dx.doi.org/10.1137/S0097539795282377 MathSciNetCrossRefMATH

Deogun, J.S., Kratsch, D.: Diametral path graphs. In: Nagl, M. (ed.) WG 1995. LNCS, vol. 1017, pp. 344–357. Springer, Heidelberg (1995). doi:10.1007/3-540-60618-1_87 CrossRef

Deogun, J.S., Kratsch, D.: Dominating pair graphs. SIAM J. Discret. Math. 15(3), 353–366 (2002). http://dx.doi.org/10.1137/S0895480100367111 MathSciNetCrossRefMATH

Dragan, F.F., Leitert, A.: On the minimum eccentricity shortest path problem. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 276–288. Springer, Heidelberg (2015). doi:10.1007/978-3-319-21840-3_23 CrossRef

10.

Lekkerkerker, C., Boland, J.: Representation of a finite graph by a set of intervals on the real line. Fund. Math. 51, 45–64 (1962)MathSciNetMATH

11.

Robertson, N., Seymour, P.D.: Graph minors. I. Excluding a forest. J. Comb. Theory Ser. B 35(1), 39–61 (1983). http://dx.doi.org/10.1016/0095-8956(83)90079-5 MathSciNetCrossRefMATH

12.

Völkel, F., Bapteste, E., Habib, M., Lopez, P., Vigliotti, C.: Read networks and k-laminar graphs. CoRR abs/1603.01179 (2016). arXiv:1603.01179

13.

Yamazaki, K., Bodlaender, H.L., Fluiter, B., Thilikos, D.M.: Isomorphism for graphs of bounded distance width. In: Bongiovanni, G., Bovet, D.P., Battista, G. (eds.) CIAC 1997. LNCS, vol. 1203, pp. 276–287. Springer, Heidelberg (1997). doi:10.1007/3-540-62592-5_79 CrossRef

14.

Yan, S., Xu, D., Zhang, B., Zhang, H., Yang, Q., Lin, S.: Graph embedding and extensions: a general framework for dimensionality reduction. IEEE Trans. Pattern Anal. Mach. Intell. 29(1), 40–51 (2007). http://dx.doi.org/10.1109/TPAMI.2007.250598 CrossRef

Title: Minimum Eccentricity Shortest Path Problem: An Approximation Algorithm and Relation with the k-Laminarity Problem
Authors: Étienne Birmelé
Fabien de Montgolfier
Léo Planche
Publisher: Springer International Publishing
Book: Combinatorial Optimization and Applications
Print ISBN: 978-3-319-48748-9

Electronic ISBN: 978-3-319-48749-6

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-319-48749-6_16

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner