research unit 1

 This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit Aigaion.nl.

Publication

Type of publication:Inproceedings
Entered by:
TitleThe Survival of the Weakest in Networks
Bibtex cite IDRACTI-RU1-2006-6
Booktitle 4th Workshop on Approximation and Online Algorithms (WAOA 2006)
Series Lecture Notes in Computer Science
Year published 2006
Month September
Pages 316-329
URL http://algo06.inf.ethz.ch/waoa/
Abstract
We study here dynamic antagonism in a fixed network, represented as a graph $G$ of $n$ vertices. In particular, we consider the case of $k \leq n$ particles walking randomly independently around the network. Each particle belongs to exactly one of two antagonistic species, none of which can give birth to children. When two particles meet, they are engaged in a (sometimes mortal) local fight. The outcome of the fight depends on the species to which the particles belong. Our problem is \emphto predict (i.e. to compute) the eventual chances of species survival. We prove here that this can indeed be done in \emphexpected polynomial time on the size of the network, provided that the network is \emphundirected.
Authors
Topics
BibTeXBibTeX
RISRIS
Attachments
 WAOA06.pdf (main file) presentationWAOA06.pdf

Publication ID44