<abstract xmlns="http://www.w3.org/1999/xhtml"><p>There has been a great deal of interest in the computation of distances and shortest paths problem in graphs which is one of the central, and most studied, problems in (algorithmic) graph theory. In this paper, we survey the exact results of the static version of the all-pairs shortest paths problem and its variants namely, the Wiener index, the average distance, and the minimum average distance spanning tree (MAD tree in short) in graphs (focusing mainly on algorithmic results for such problems). Along the way we also mention some important open issues and further research directions in these areas.</p></abstract>

There has been a great deal of interest in the computation of distances and shortest paths problem in graphs which is one of the central, and most studied, problems in (algorithmic) graph theory. In this paper, we survey the exact results of the static version of the all-pairs shortest paths problem and its variants namely, the Wiener index, the average distance, and the minimum average distance spanning tree (MAD tree in short) in graphs (focusing mainly on algorithmic results for such problems). Along the way we also mention some important open issues and further research directions in these areas.

A survey of the all-pairs shortest paths problem and its variants in graphs

Department of Computer Science and Engineering, NMAM Institute of Technology, Nitte–574 110, India.

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"A survey of the all-pairs shortest paths problem and its variants in graphs"}

There has been a great deal of interest in the computation of distances and shortest paths problem in graphs which is one of the central, and most studied,...

A survey of the all-pairs shortest paths problem and its variants in graphs

Publié en ligne: 20 juin 2016

Pages: 16 - 40

Reçu: 13 févr. 2016

DOI: https://doi.org/10.1515/ausi-2016-0002

Mots clés
algorithms, all-pairs shortest paths, average distance, graph algorithms, MAD tree, spanning tree, Wiener index

© 2016 K. R. Udaya Kumar Reddy, published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

A survey of the all-pairs shortest paths problem and its variants in graphs

Publié en ligne: 20 juin 2016

Pages: 16 - 40

Reçu: 13 févr. 2016

DOI: https://doi.org/10.1515/ausi-2016-0002

Mots clésalgorithms, all-pairs shortest paths, average distance, graph algorithms, MAD tree, spanning tree, Wiener index

© 2016 K. R. Udaya Kumar Reddy, published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Mots clés
algorithms, all-pairs shortest paths, average distance, graph algorithms, MAD tree, spanning tree, Wiener index