Graphs and Path Equilibria

Abstract : The quest for optimal/stable paths in graphs has gained attention in a few practical or theoretical areas. To take part in this quest this chapter adopts an equilibrium-oriented approach that is abstract and general: it works with (quasi-arbitrary) arc-labelled digraphs, and it assumes very little about the structure of the sought paths and the definition of equilibrium, \textit{i.e.} optimality/stability. In this setting, this chapter presents a sufficient condition for equilibrium existence for every graph; it also presents a necessary condition for equilibrium existence for every graph. The necessary condition does not imply the sufficient condition a priori. However, the chapter pinpoints their logical difference and thus identifies what work remains to be done. Moreover, the necessary and the sufficient conditions coincide when the definition of optimality relates to a total order, which provides a full-equivalence property. These results are applied to network routing.
Type de document :
[Research Report] 2007, pp.41
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger
Contributeur : Stéphane Le Roux <>
Soumis le : lundi 10 décembre 2007 - 16:13:22
Dernière modification le : mardi 24 avril 2018 - 13:52:28
Document(s) archivé(s) le : lundi 12 avril 2010 - 06:48:09


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


  • HAL Id : inria-00195379, version 1
  • ARXIV : 0712.1521



Stéphane Le Roux. Graphs and Path Equilibria. [Research Report] 2007, pp.41. 〈inria-00195379〉



Consultations de la notice


Téléchargements de fichiers