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
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