Algebraic Routing (Part 1)

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

• Tim Griffin
• Monday 13 November 2006, 10:00-12:00
• Computer Laboratory, Room FW11.

If you have a question about this talk, please contact Sam Staton.

It has been known for several decades that shortest-paths algorithms such as those of Bellman-Ford and Dijkstra can be generalized to commutative and idempotent semirings. This course will review the basics of this theory, as well as some further generalizations that go beyond semirings. For the core material I will attempt to condense those parts of the 2001 book

• Graphes, dioides et semi-anneaux : Nouveaux modèles et algorithmes by Michel Gondran, Michel Minoux

which I have found to be most relevant to network routing. No previous knowledge of the area will be assumed.

This talk is part of the Mini Courses in Theoretical Computer Science series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• All transferable skills in the university: computing
• Cambridge talks
• Computer Laboratory, Room FW11
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Mini Courses in Theoretical Computer Science
• Modelling Biology
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.