Campus Event Calendar
Event Entry
What and Who
The polygon representation of near-minimum cuts
Michel Goemans
University of Louvain and MIT
AG1 Mittagsseminar
AG 1, AG 2
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 5 December 97
13:30
60 Minutes
MPI
024
Saarbrücken
Abstract
In this talk, I will describe the polygon representation of all cuts
of value less than 6/5 times the value of the minimum in an undirected
graph. This representation, discovered by Andras Benczur, is a
geometric representation of a collection of sets by diagonals of a
polygon in the plane. The representation extends the classical cactus
representation of Dinitz, Karzanov, and Lomonosov for all minimum
cuts. The proof of existence of the polygon representation will be
sketched.
This is joint work with Andras Benczur.
Contact
Naveen Garg
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
45 minutes, partly black board.