Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:An approximation Algorithm for Weighted Weak Vertex Cover
Speaker:Hong Zhu
coming from:Fudan University, Shanghai, China
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D4, D2, D5, D3
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Friday, 30 January 2004
Time:13:30
Duration:-- Not specified --
Location:Saarbr├╝cken
Building:46.1 - MPII
Room:024
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
Name(s):Peter Sanders
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Peter Sanders, 01/20/2004 01:35 PM -- Created document.