Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2018) | last year (2017) | two years ago (2016) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Doerr, Benjamin
Johannsen, Daniel

dblp
dblp



Editor(s):

Thierens, Dirk

dblp

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

URL of the conference:

http://www.sigevo.org/gecco-2007/

URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
DoerrJohannsen_2007_AdjacencyListMatchings-AnIdealGenotypeForCycleCovers.pdf