The Oberwolfach Problem OP (F)-posed by Gerhard Ringel in 1967-is a paradigmatic Combinatorial Design problem asking whether the complete graph K-v decomposes into edge-disjoint copies of a 2-regular graph F of order v. In this paper we provide all the necessary equipment to generate solutions to OP (F) for relatively small orders by using so-called difference methods. From the theoretical standpoint, we present new insights on the combinatorial structures involved in the solution of the problem. Computationally, we provide a full recipe whose base ingredients are advanced optimization models and tailored algorithms. This algorithmic arsenal can solve the OP (F) for all possible orders up to 60 with the modest computing resources of a personal computer. The 20 new orders, from 41 to 60, encompass 241 200 instances of the Oberwolfach Problem, which is 22 times greater than those solved in previous contributions.

Merging combinatorial design and optimization: the Oberwolfach Problem

Traetta, T;Buratti, M
;
2021

Abstract

The Oberwolfach Problem OP (F)-posed by Gerhard Ringel in 1967-is a paradigmatic Combinatorial Design problem asking whether the complete graph K-v decomposes into edge-disjoint copies of a 2-regular graph F of order v. In this paper we provide all the necessary equipment to generate solutions to OP (F) for relatively small orders by using so-called difference methods. From the theoretical standpoint, we present new insights on the combinatorial structures involved in the solution of the problem. Computationally, we provide a full recipe whose base ingredients are advanced optimization models and tailored algorithms. This algorithmic arsenal can solve the OP (F) for all possible orders up to 60 with the modest computing resources of a personal computer. The 20 new orders, from 41 to 60, encompass 241 200 instances of the Oberwolfach Problem, which is 22 times greater than those solved in previous contributions.
2021
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/1501571
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 7
social impact