Campus Event Calendar
Event Entry
What and Who
Faster algorithms for all-pairs min cuts
Kavitha Telikepalli
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 16 July 2008
14:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
I will present some recent work on faster algorithms for
computing all-pairs min cuts in a unit capacitated undirected graph G.
We show that a Gomory-Hu tree of G can be constructed in
O(mn.poly(logn)) time where m is the number of edges and n is the
number of vertices in G. This uses a faster algorithm for computing a
minimum Steiner cut.
Contact
Khaled Elbassioni
--email hidden
passcode not visible
logged in users only
Khaled Elbassioni, 07/14/2008 11:52 -- Created document.