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