Shortest Path Discovery Problem, Revisited (Query Ratio, Upper and Lower Bounds)

Olivier Brun 1 Josu Doncel 1 Christopher Thraves-Caro 1
1 LAAS-SARA - Équipe Services et Architectures pour Réseaux Avancés
LAAS - Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
Abstract : Consider the following problem: given two nodes s and t in a fully connected graph where each edge of the graph has a hidden length, discover the shortest path between s and t. The issue is that edge lengths are hidden. Hence, any algorithm that aims to solve the problem needs to uncover the length of some edges to discover the shortest path. The goal then is to discover the shortest path by means of uncovering the least possible amount of edge lengths. This problem is known as the Shortest Path Discovery (SPD) problem. The SPD problem is introduced by [13] in AAAI 2004. In this document, we study the SPD problem. We show that the previously proposed measure to evaluate the quality of an algo-rithm does not differentiate correctly algorithms according to their per-formance. Hence, it does not provide insightful information. Therefore, we introduce the query ratio, the ratio between the number of uncovered edge lengths and the least number of edge lengths required to solve the problem, as a new measure to evaluate algorithms that solve the SPD problem. When an input of size n is considered, we prove a lower bound of 1 + 4/n − 8/n 2 on the query ratio of any algorithm that solves the SPD problem. As well, we present an algorithm that solves the problem and we prove that its query ratio is equal to 2 − 1/(n − 1).
Type de document :
[Research Report] LAAS-CNRS. 2014
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger
Contributeur : Chrsitopher Thraves Caro <>
Soumis le : mercredi 22 octobre 2014 - 16:45:20
Dernière modification le : mercredi 28 février 2018 - 10:23:12
Document(s) archivé(s) le : vendredi 23 janvier 2015 - 11:11:43


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01076628, version 1


Olivier Brun, Josu Doncel, Christopher Thraves-Caro. Shortest Path Discovery Problem, Revisited (Query Ratio, Upper and Lower Bounds). [Research Report] LAAS-CNRS. 2014. 〈hal-01076628〉



Consultations de la notice


Téléchargements de fichiers