MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Doerr, Benjamin
Johannsen, Daniel
dblp
dblp
Editor(s):
Thierens, Dirkdblp
Not MPII Editor(s):
Thierens, Dirk
BibTeX cite key*:
DoerrJohannsen07a
Title, Booktitle
Title*:
Adjacency List Matchings --- An Ideal Genotype for Cycle Covers
DoerrJohannsen_2007_AdjacencyListMatchings-AnIdealGenotypeForCycleCovers.pdf (222.55 KB)
Booktitle*:
Genetic and Evolutionary Computation Conference (GECCO-2007)
Event, URLs
Conference URL::
http://www.sigevo.org/gecco-2007/
Downloading URL:
Event Address*:
London, UK
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
7 July 2007
Event End Date:
11 July 2007
Publisher
Name*:
ACM
URL:
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
1203-1210
Year*:
2007
VG Wort Pages:
12
ISBN/ISSN:
978-1-59593-697-4
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We propose and analyze a novel genotype representation for walk and cycle covers in graphs. Together with a natural mutation operator, it yields superior algorithms based on randomized local search and (1+1) evolutionary algorithms. In particular, we derive an evolutionary algorithm that computes an Euler tour in a graph with $m$ edges in expected run-time $O(m \log m)$. This is comparable to the best direct algorithm for this problem running in linear time. Also, a simple coupon collector argument indicates that our run-time is asymptotically optimal for any randomized search heuristic.
Keywords:
Evolutionary Algorithm, Randomized Local Search, Euler tour, Runtime Analysis
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
popular
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{DoerrJohannsen07a,
AUTHOR = {Doerr, Benjamin and Johannsen, Daniel},
EDITOR = {Thierens, Dirk},
TITLE = {Adjacency List Matchings --- An Ideal Genotype for Cycle Covers},
BOOKTITLE = {Genetic and Evolutionary Computation Conference (GECCO-2007)},
PUBLISHER = {ACM},
YEAR = {2007},
PAGES = {1203--1210},
ADDRESS = {London, UK},
ISBN = {978-1-59593-697-4},
}


Entry last modified by Daniel Johannsen, 02/15/2009
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Daniel Johannsen
Created
03/15/2007 10:53:01 AM
Revisions
8.
7.
6.
5.
4.
Editor(s)
Daniel Johannsen
Daniel Johannsen
Mathias Bader
Mathias Bader
Mathias Bader
Edit Dates
02/15/2009 07:52:13 PM
30.01.2008 13:57:01
31.07.2007 08:21:54
24.07.2007 11:40:54
04.04.2007 19:26:35


File Attachment Icon
DoerrJohannsen_2007_AdjacencyListMatchings-AnIdealGenotypeForCycleCovers.pdf