Campus Event Calendar
Event Entry
What and Who
An approximation Algorithm for Weighted Weak Vertex Cover
Hong Zhu
Fudan University, Shanghai, China
AG1 Mittagsseminar (own work)
AG 1, AG 4, AG 2, AG 5, AG 3
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 30 January 2004
13:30
-- Not specified --
46.1 - MPII
024
Saarbrücken
Abstract
The problem of efficiently monitoring the network flow is regarded as the one to find out the minimum
weighted weak vertex cover set for a given graph G. We show that a weak vertex cover set approximating a minimum one within
2-2/nu(G) can be efficiently found in undirected graphs, and improve the previous work from approximation ratio within ln(d) + 1, where
d is the maximum degree of the vertex in graph G.
Contact
Peter Sanders
--email hidden
passcode not visible
logged in users only
Peter Sanders, 01/20/2004 13:35 -- Created document.