PORTO @ Archivio Istituzionale della Ricerca

IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.

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 Combinatorial Design Theory, so-called difference methods represent a well-known solution technique and construct solutions in infinitely many cases exploiting symmetric and balanced structures. This approach reduces the problem to finding a well-structured $2$-factor which allows us to build solutions that we call $1$- or $2$-rotational according to their symmetries. We tackle $OP$ by modeling difference methods with Optimization tools, specifically Constraint Programming ($CP$) and Integer Programming ($IP$), and correspondingly solve instances with up to $v=120$ within $60s$. In particular, we model the $2$-rotational method by solving in cascade two subproblems, namely the binary and group labeling, respectively. A polynomial-time algorithm solves the binary labeling, while $CP$ tackles the group labeling. Furthermore, we prov ide necessary conditions for the existence of some $1$-rotational solutions which stem from computational results. This paper shows thereby that both theoretical and empirical results may arise from the interaction between Combinatorial Design Theory and Operation Research.

Merging Combinatorial Design and Optimization: the Oberwolfach Problem / Salassa, Fabio Guido Mario; Dragotto, Gabriele; Traetta, Tommaso; Buratti, Marco; Della Croce Di Dojola, Federico. - In: THE AUSTRALASIAN JOURNAL OF COMBINATORICS. - ISSN 2202-3518. - 79(2021), pp. 141-166.

Powered by IRIS-about IRIS-Utilizzo dei cookie

 Copyright © 2021