Campus Event Calendar
Event Entry
What and Who
A fast algorithm for computing steiner edge connectivity" (Published in STOC 2003. Author : Cole-Ramesh)
Anand Bhalgat
Max-Planck-Institut für Informatik - D 1
AG1 Mittagsseminar (others' work)
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
-- Not specified --
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 23 June 2006
13:30
-- Not specified --
E1 4
023
Saarbrücken
Abstract
This is a result from the paper "A fast algorithm for computing steiner edge connectivity" (Richard Cole, Ramesh Hariharan. STOC 2003). Given a graph G either undirected or eulerian and a subset of vertices of the graph S, steiner connectivity of S is the edge connectivity of vertices in S(minimum value of cut in G separating the vertices of S). The paper presents an algorithm to compute the steiner connectivity k of vertices in S. The complexity of the algorithm is linear in n.(O(nk^3+m)). The algorithm is based on efficient construction of tree packing which uses a generalization of Edmond's tree packing theorem. The result can be used to
compute efficiently the cactus tree representing all significant steiner cuts which can used for fast implementation of approximation algorithm the survivable network design problem due to Goemans, Williamson and Mihail Vazirani.
Contact
Khaled Elbassioni
--email hidden
passcode not visible
logged in users only
Khaled Elbassioni, 06/19/2006 13:57 -- Created document.