Output details
11 - Computer Science and Informatics
University of Liverpool
Article title
Approximating Fixation Probabilities in the Generalized Moran Process
Type
D - Journal article
Title of journal
Algorithmica
Article number
-
Volume number
2012
Issue number
-
First page of article
-
ISSN of journal
1432-0541
Year of publication
2013
URL
-
Number of additional authors
5
Additional information
<12>A preliminary version of this paper appeared in SODA 2012. We examine a model of evolutionary processes in networks that was introduced by Nowak et. al. in Nature 2005. We answer positively a key question left open by that work, by showing that the fixation probability can be computed efficiently by a fully polynomial randomized approximation scheme. Mertzios and Spirakis (ICALP 2013) build on our work to resolve two further open questions: the nonexistence of strong amplifiers for undirected graphs and the best-known lower bound on the fixation probability when the mutant starts from a vertex of known degree.
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
0
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
