CS 594 Graph Algorithms

Suggestions for implementations

• Implement and experimantally evaluate Karger's algorithm for Min-Cut. Compare this algorithm to an algorithm based on Max-Flow/Min-Cut duality.
• Implement and experimentally evaluate the algorithm of Dahlhaus et al. for Multiway Cut.
• Min-Cut and Multiway Cut can be used for image segmentation. Experimentally evaluate this approach.
• Implement and experimantally evaluate the algorithm of Leighton and Rao for computing balanced cuts. Use this algorithm to approximate Minimum Linear Arrangement.
• Implement and experimantally evaluate the algorithm for TSP based on the Pointer Networks paper.

Suggestions for paper presentations

• J. Kleinberg. Authoritative sources in a hyperlinked environment. JACM, 1999.
• D. Rotter and J. Vygen. d-Dimensional arrangement revisited. IPL, 2013.
• J. Kleinberg. The small-world phenomenon: An algorithmic perspective. STOC, 2000.
• J. Kleinberg. Inferring Web Communities from Link Topology.
• D. Liben-Nowell, J. Kleinberg. The Link Prediction Problem for Social Networks.
• O. Svensson, J. Tarnawski, L. Vegh. A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem.
• R. Duan, S. Pettie, H. Su. Scaling Algorithms for Weighted Matching in General Graphs.