HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Monday, December 10, 2007 - 4:13:22 PM
Last modification on : Friday, September 10, 2021 - 2:34:03 PM
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

111

Files downloads

170