Adjacency List Matchings --- An Ideal Genotype for Cycle Covers

Doerr, Benjamin; Johannsen, Daniel

doi:10.1145/1276958.1277192

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Adjacency List Matchings --- An Ideal Genotype for Cycle Covers

MPS-Authors

/persons/resource/persons44338

Doerr, Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44705

Johannsen, Daniel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Doerr, B., & Johannsen, D. (2007). Adjacency List Matchings --- An Ideal Genotype for Cycle Covers. In D. Thierens (Ed.), GECCO 2007: Genetic and Evolutionary Computation Conference. - Vol. 1 (pp. 1203-1210). New York, NY: ACM. doi:10.1145/1276958.1277192.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-1DE3-7

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.