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. Conferences, Workshops, Symposiums, and Seminars
  4. Minimizing breaks in incomplete round-robin tournaments
 
conference paper

Minimizing breaks in incomplete round-robin tournaments

de Werra, Dominique  
•
Urrutia, Sebastián
•
Assunção, Lucas
Grippo, Luciano N.
•
Safe, Martin D.
2025
Procedia Computer Science : XIII Latin American Algorithms, Graphs, and Optimization Symposium (LAGOS 2025)
13 Latin American Algorithms, Graphs, and Optimization Symposium (LAGOS 2025)

In round-robin schedules, a break occurs when a team plays two consecutive home or two consecutive away games. Minimizing breaks is important for ensuring competitive fairness and logistical efficiency. This article addresses the problem of minimizing breaks in incomplete round-robin schedules in which each pair of teams plays again each other at most once. The problem of minimizing breaks is a classical problem that was previously thoroughly studied in the context of complete round-robin schedules. Using a graph-theoretic model we analyze structural properties of incomplete round-robin schedules. We derive some bounds on the minimum number of breaks. Then, we propose an algorithm that is able to construct incomplete single round-robin schedules minimizing the number of breaks for given numbers of teams and rounds if the number of rounds is not larger than 3/4 of the number of teams.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1016/j.procs.2025.10.285
Scopus ID

2-s2.0-105023470509

Author(s)
de Werra, Dominique  

EPFL

Urrutia, Sebastián

Høgskolen i Molde

Assunção, Lucas

Université Le Havre Normandie

Editors
Grippo, Luciano N.
•
Safe, Martin D.
Date Issued

2025

Publisher

Elsevier B.V.

Published in
Procedia Computer Science : XIII Latin American Algorithms, Graphs, and Optimization Symposium (LAGOS 2025)
Series title/Series vol.

Procedia Computer Science; 273

ISSN (of the series)

1877-0509

Start page

94

End page

101

Subjects

break minimization

•

Incomplete round robin

•

sports scheduling

•

tournaments

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
TRANSP-OR  
Event nameEvent acronymEvent placeEvent date
13 Latin American Algorithms, Graphs, and Optimization Symposium (LAGOS 2025)

LAGOS 2025

Buenos Aires, Argentina

2025-11-10 - 2025-11-14

FunderFunding(s)Grant NumberGrant URL

Molde University College

EPFL

European Union's Horizon 2020 research and innovation program

Show more
Available on Infoscience
December 9, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/256893
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