2019/03/28 by Salassa, Fabio, Dragotto, Gabriele, Traetta, Tommaso +2
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1903.12112
The Oberwolfach Problem OP(F) -- posed by Gerhard Ringel in 1967 -- is a paradigmatic Combinatorial Design problem asking whether the complete graph Kv 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 the 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 new 20 orders, from 41 to 60, encompass 241200 instances of the Oberwolfach Problem, which is 22 times greater than those solved in previous contributions.