Course pages 2018–19
Algebraic Path Problems, with applications to Internet Routing
Lecture slides
- Lectures 1 and 2.
- slides, 1 per page.
- slides, 2 per page.
- Interesting related links ...
- Lecture 3.
- slides, 1 per page.
- slides, 2 per page.
- Interesting related links ...
- Lecture 4.
- slides, 1 per page.
- slides, 2 per page.
- Interesting related links ...
- A Gaussian Elimination Algorithm for the Enumeration of Cut Sets in a Graph. Alberto Martelli. Journal of the ACM (JACM). Volume 23, Issue 1, Jan. 1976.
- Minimum-Cost Spanning Tree as a Path-Finding Problem
- Lecture 5.
- Lecture 6.
- Lecture 7.
- Lecture 8.
- Lecture 9.
- Lecture 10.
- Lectures 11 and 12. We discussed this paper.
- Lecture 13.
- Lecture 14.
- slides, 1 per page.
- slides, 2 per page.
- Please read this paper before lecture 15.
On reserve in CL library
- Path problems in networks. John S. Baras and George Theodorakopoulos. Morgan and Claypool, 2010.
- Graphs, Dioids and Semirings : New Models and Algorithms, by Michel Gondran , Michel Minoux, 2008
Reading
- RFC 1058: Routing Information Protocol (RIP). C. Hedrick (1988)
- An Algebra for Network Routing Problems. B. A. CARRÉ (1970).
- Semiring frameworks and algorithms for shortest-distance problems, M. Mohri
- On the Forwarding Paths Produced by Internet Routing Algorithms. Seweryn Dynerowicz (University of Namur, Belgium), Timothy G. Griffin. ICNP 2013.
- A Gaussian Elimination Algorithm for the Enumeration of Cut Sets in a Graph. Alberto Martelli. Journal of the ACM (JACM). Volume 23, Issue 1, Jan. 1976.