Max-Planck-Institut für Informatik
max planck institut
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:The probability of a rendezvous is minimal in complete graphs
Speaker:Martin Dietzfelbinger
coming from:Techn. Univ. Ilmenau, currently guest at AG 1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Wednesday, 15 May 2002
Duration:45 Minutes
Building:46.1 - MPII
In an arbitrary simple graph G of n >= 2 nodes the

following random experiment is carried out: each node chooses one
of its neighbors uniformly at random. We say a rendezvous occurs
if there are adjacent nodes u and v such that u chooses v
and v chooses u . It was posed as an open problem by
Metivier et al. if the probability for a rendezvous
to occur in G is at least as large as the probability of a rendezvous
if the same experiment is carried out in the complete graph on n
nodes. We discuss the problem and prove the statement. -

Name(s):Martin Dietzfelbinger
Phone:- 516
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Keywords:algorithm analysis, randomized algorithms, networks, graphs
Attachments, File(s):