Merging combinatorial design and optimization: the Oberwolfach problem

MaRDI QIDQ4990113zbMATH OpenFDO

Authors Fabio Salassa, Gabriele Dragotto, Tommaso Traetta, Marco Buratti, F. Della Croce

Publication date 28 May 2021

Full work available at URL https://arxiv.org/abs/1903.12112, http://ajc.maths.uq.edu.au/pdf/79/ajc_v79_p141.pdf

zbMATH Keywords

combinatorial designgraph partitioning

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

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

Recommendations

• scientific article; zbMATH DE number 5917757
• Note on three table Oberwolfach problem
• SOME RESULTS ON THE OBERWOLFACH PROBLEM
• Resolution of the Oberwolfach problem
• scientific article; zbMATH DE number 6452866

Cites work

• 1‐rotational k‐factorizations of the complete graph and new solutions to the Oberwolfach problem
• 2-starters, graceful labelings, and a doubling construction for the Oberwolfach problem
• A complete solution to the two-table Oberwolfach problems
• A non-existence result on cyclic cycle-decompositions of the cocktail party graph
• Complete solutions to the Oberwolfach problem for an infinite set of orders
• From graceful labellings of paths to cyclic solutions of the Oberwolfach problem
• scientific article; zbMATH DE number 5917757 (Why is no real title available?)
• scientific article; zbMATH DE number 867473 (Why is no real title available?)
• scientific article; zbMATH DE number 3349817 (Why is no real title available?)
• On a variation of the Oberwolfach problem
• On bipartite 2-factorizations of \(K_{n} - I\) and the Oberwolfach problem
• On sharply vertex transitive 2-factorizations of the complete graph
• Some observations on the oberwolfach problem
• SOME RESULTS ON THE OBERWOLFACH PROBLEM
• The existence of \(C_ k\)-factorizations of \(K_{2n}-F\)
• The Oberwolfach problem and factors of uniform odd length cycles
• The solution of the bipartite analogue of the Oberwolfach problem
• The structure of 2-pyramidal 2-factorizations
• The table placement problem: a research challenge at the EWI 2007
• Two-factorizations of the complete graph

Cited in

(15)

• Resolution of the Oberwolfach problem
• On the Oberwolfach problem for single-flip 2-factors via graceful labelings
• A greedy algorithm for the social golfer and the Oberwolfach problem
• On the directed Oberwolfach problem for complete symmetric equipartite digraphs and uniform‐length cycles
• Resolvable cycle decompositions of complete multigraphs and complete equipartite multigraphs via layering and detachment
• A complete solution to the infinite Oberwolfach problem
• A constructive solution to the Oberwolfach problem with a large cycle
• Solutions to the Oberwolfach problem for orders up to 100
• The Oberwolfach problem with loving couples
• A survey on constructive methods for the Oberwolfach problem and its variants
• Completing the solution of the directed Oberwolfach problem with two tables
• A solution to small cases of the honeymoon Oberwolfach problem
• The directed Oberwolfach problem with variable cycle lengths: a recursive construction
• On the directed Hamilton-Waterloo problem with two cycle sizes
• Transforming solutions for the Oberwolfach problem into solutions for the spouse-loving variant

This page was built for publication: Merging combinatorial design and optimization: the Oberwolfach problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4990113)