Skip to Main content Skip to Navigation
Reports

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.
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download

https://hal.inria.fr/inria-00195379
Contributor : Stéphane Le Roux <>
Submitted on : Monday, December 10, 2007 - 4:13:22 PM
Last modification on : Thursday, November 21, 2019 - 2:14:17 AM
Long-term archiving on: : Monday, April 12, 2010 - 6:48:09 AM

Files

graph_optim_report.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

187

Files downloads

247