Convergence of path-finding

Add to your list(s) Download to your calendar using vCal

• Alex Gurney
• Monday 24 November 2008, 12:45-14:00
• FW26.

If you have a question about this talk, please contact Matthew Parkinson.

It is well-known that finding shortest paths in a graph corresponds to solving a matrix equation, and that this can be done by an iterative process. This is guaranteed to converge to a fixed point if the underlying algebra of the matrix elements has certain properties.

We will look at the related notion of a “stable paths problem”, where the solution that is sought is not an optimal shortest-paths tree, but a Nash equilibrium of path assignments. The same matrix methods can be used to solve this problem, but the algebraic properties involved are different.

This talk will concentrate on proofs of convergence for the matrix iteration, and the associated problem of how many iteration steps may be required before a fixed point is reached.

This talk is part of the Semantics Lunch (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Computer Laboratory talks
• FW26
• School of Technology
• Semantics Lunch (Computer Laboratory)
• de239's list

Note that ex-directory lists are not shown.