Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Recoloring subgraphs of K-2n for sports scheduling
 
research article

Recoloring subgraphs of K-2n for sports scheduling

Urrutia, Sebastian
•
de Werra, Dominique  
•
Januario, Tiago
July 20, 2021
Theoretical Computer Science

The exploration of one-factorizations of complete graphs is the foundation of some classical sports scheduling problems. One has to traverse the landscape of such one-factorizations by moving from one of those to a so-called neighbor one-factorization. This approach amounts to modifying locally the coloring associated with a one-factorization. We consider some particular types of modifications and describe various constructions which give one-factorizations which may be modified or not by these techniques. Among those are recoloring of bichromatic cycles, altering of optimally colored subcliques of even size, or recoloring of chordless lanterns. (C) 2021 The Author(s). Published by Elsevier B.V.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.tcs.2021.03.029
Web of Science ID

WOS:000656664500003

Author(s)
Urrutia, Sebastian
de Werra, Dominique  
Januario, Tiago
Date Issued

2021-07-20

Publisher

ELSEVIER

Published in
Theoretical Computer Science
Volume

877

Start page

36

End page

45

Subjects

Computer Science, Theory & Methods

•

Computer Science

•

graph theory

•

one-factorization

•

subgraph recoloring

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
ROSE  
Available on Infoscience
June 19, 2021
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/179181
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés