---
res:
  bibo_abstract:
  - The edge coloring problem asks for an assignment of colors to edges of a graph
    such that no two incident edges share the same color and the number of colors
    is minimized. It is known that all graphs with maximum degree {$\Delta$} can be
    colored with {$\Delta$} or {$\Delta$} + 1 colors, but it is NP-hard to determine
    whether {$\Delta$} colors are sufficient. We present the first runtime analysis
    of evolutionary algorithms (EAs) for the edge coloring problem. Simple EAs such
    as RLS and (1+1) EA efficiently find (2{$\Delta$} - 1)-colorings on arbitrary
    graphs and optimal colorings for even and odd cycles, paths, star graphs and arbitrary
    trees. A partial analysis for toroids also suggests efficient runtimes in bipartite
    graphs with many cycles. Experiments support these findings and investigate additional
    graph classes such as hypercubes, complete graphs and complete bipartite graphs.
    Theoretical and experimental results suggest that simple EAs find optimal colorings
    for all these graph classes in expected time O({$\Delta\mathscrl$}2m log m), where
    m is the number of edges and {$\mathscrl$} is the length of the longest simple
    path in the graph.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Jakob
      foaf_name: Bossek, Jakob
      foaf_surname: Bossek
      foaf_workInfoHomepage: http://www.librecat.org/personId=102979
    orcid: 0000-0002-4121-4668
  - foaf_Person:
      foaf_givenName: Dirk
      foaf_name: Sudholt, Dirk
      foaf_surname: Sudholt
  bibo_doi: 10.1145/3299904.3340311
  dct_date: 2019^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/978-1-4503-6254-2
  dct_language: eng
  dct_publisher: Association for Computing Machinery@
  dct_subject:
  - edge coloring problem
  - runtime analysis
  dct_title: Time Complexity Analysis of RLS and (1 + 1) EA for the Edge Coloring
    Problem@
...