Publications de Dominique de Werra

A tutorial on graph models for scheduling round-robin sports tournaments

Many sports leagues organize their competitions as round-robin tournaments. This tournament design has a rich mathematical structure that has been studied in the literature over the years. We review some of the main properties and fundamental scheduling me ...

WILEY2023

The micro-world of cographs

Dominique de Werra

Cographs constitute a small point in the atlas of graph classes. However, by zooming in on this point, we discover a complex world, where many parameters jump from finiteness to infinity. In the present paper, we identify several milestones in the world of ...

ELSEVIER2022

Recoloring subgraphs of K-2n for sports scheduling

Dominique de Werra

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. Thi ...

ELSEVIER2021

Letter graphs and geometric grid classes of permutations: Characterization and recognition

Dominique de Werra

In this paper, we reveal an intriguing relationship between two seemingly unrelated notions: letter graphs and geometric grid classes of permutations. An important property common for both of them is well-quasi-orderability, implying, in a non-constructive ...

ELSEVIER2020

Minimal graphs for 2-factor extension

Dominique de Werra

Let G = (V, E) be a simple loopless finite undirected graph. We say that G is (2-factor) expandable if for any non-edge uv, G + uv has a 2-factor F that contains uv. We are interested in the following: Given a positive integer n = vertical bar V vertical b ...

ELSEVIER2020

Dominating induced matchings in graphs containing no long claw

Dominique de Werra, Bernard Ries

2018

Minimal graphs for matching extensions

Dominique de Werra

2018

What are the worst cases in constrained Last-In-First-Out pick-up and delivery problems?

Dominique de Werra

2018

Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition

Dominique de Werra

In this paper, we reveal an intriguing relationship between two seemingly unrelated notions: letter graphs and geometric grid classes of permutations. We also present the first constructive polynomial-time algorithm for the recognition of 3-letter graphs. ...

SPRINGER INTERNATIONAL PUBLISHING AG2018

Sports scheduling search space connectivity: A riffle shuffle driven approach

Dominique de Werra

The canonical method is widely used to build single round robin schedules for sports competitions. Certain properties of the canonical method may entrap local search procedures. In this paper, we study the connectivity of one of the most used neighborhood ...

Elsevier Science Bv2016