Min Cut Information

[Guillermo]

Hey all,

As a precursor to the Randomized Min-Cut, I would like everyone to at
least understand what a graph is. The wikipedia page
http://en.wikipedia.org/wiki/Graph_(mathematics) is sufficient at
explaining.

I will be taking a similar approach to Stephen's discussion. I will
first go over the Min-Cut problem and its deterministic solution. To
understand the deterministic solution, I would like everyone to get a
feeling of the max flow problem and solution.
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow
provides a great intro to max flow.

Afterwards, I will talk about the Randomized Min-Cut by Edge
Contraction. For the most part I will follow this pdf which covers it
pretty simply: https://docs.google.com/viewer?url=http://www.cs.virginia.edu/~evans/cs216/classes/lecture26.ppt

If there is time and I manage to find an easy way to teach this, I
will discuss the main algorithm discussed in this paper:
http://arxiv.org/pdf/cs/9812007

Hope to see you guys there,

Guillermo Gomez

[Guillermo]

Hey all,

Forgot to mention, this will be NEXT Friday, the 11th. Not tomorrow!

Thanks,

Guillermo Gomez

On Feb 3, 11:07 am, Guillermo <guille0...@gmail.com> wrote:
> Hey all,
>
> As a precursor to the Randomized Min-Cut, I would like everyone to at

> least understand what a graph is. The wikipedia pagehttp://en.wikipedia.org/wiki/Graph_(mathematics) is sufficient at

> explaining.
>
> I will be taking a similar approach to Stephen's discussion. I will
> first go over the Min-Cut problem and its deterministic solution. To
> understand the deterministic solution, I would like everyone to get a

> feeling of the max flow problem and solution.http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow

> provides a great intro to max flow.
>
> Afterwards, I will talk about the Randomized Min-Cut by Edge
> Contraction. For the most part I will follow this pdf which covers it

> pretty simply:https://docs.google.com/viewer?url=http://www.cs.virginia.edu/~evans/...