Fw: deterministic alg for Min-Cut

[sarthak...@gmail.com]

Sent on my BlackBerry® from Vodafone

---

From: Rajiv Gandhi <raji...@gmail.com>

Date: Wed, 14 Dec 2011 13:02:39 -0500

To: sarthak gupta<sarthak...@gmail.com>

Cc: Tanvi Nabar<tanvi...@gmail.com>; Soham Shah<soham...@gmail.com>; Amit Chavan<cam...@gmail.com>; sudha rao<raosu...@gmail.com>; Kartik<karti...@gmail.com>; amey bhangale<amu....@gmail.com>

Subject: deterministic alg for Min-Cut

Sarthak,

Please post the following message.

There is a deterministic alg for min-cut due to Stoer and Wagner (came a few years after Karger's randomized alg) which is also quite nice and simple. I suggest that you guys read this paper after I am gone.

The paper is attached.

One of my students prepared a nice presentation of the result. I suggest that one of you present it to the whole class. The presentation can be found at:

http://crab.rutgers.edu/~rajivg/talks.html     (look for "A Simple Min-Cut Algorithm").

Rajiv