Jan Goedgebeur

Gauvain Devillez, Sven D'hondt, Jan Goedgebeur

The House of Graphs is an online database of graphs which can be accessed at https://houseofgraphs.org/. It serves as a central repository for complete lists of graphs for various graph classes. However, its main feature is a searchable database of so-called "interesting" graphs. The development of the original House of Graphs started in 2010 and it was completely rebuilt in 2021-2022. Each graph in the database is accompanied by a significant amount of meta-data such as a name, drawings, precomputed graph invariants, and comments. Given this volume of information and the importance of reliability in the scientific world, robust data management is essential to ensure accuracy and consistency across the database. In this article, we therefore focus on knowledge management in the House of Graphs and describe the inner workings of the House of Graphs and how we ensure that its data is coherent, qualitative and stable.

Stijn Cambie, Jan Goedgebeur, Jorik Jooken et al.

For integers $k,g,d$, a $(k;g,d)$-cage (or simply girth-diameter cage) is a smallest $k$-regular graph of girth $g$ and diameter $d$ (if it exists). The order of a $(k;g,d)$-cage is denoted by $n(k;g,d)$. We determine asymptotic lower and upper bounds for the ratio between the order and the diameter of girth-diameter cages as the diameter goes to infinity. We also prove that this ratio can be computed in constant time for fixed $k$ and $g$. We theoretically determine the exact values $n(3;g,d)$, and count the number of corresponding girth-diameter cages, for $g \in \{4,5\}$. Moreover, we design and implement an exhaustive graph generation algorithm and use it to determine the exact order of several open cases and obtain -- often exhaustive -- sets of the corresponding girth-diameter cages. The largest case we generated and settled with our algorithm is a $(3;7,35)$-cage of order 136.

Louis Stubbe, Jens Goemaere, Jan Goedgebeur

Automated guided vehicles (AGVs) are widely used in various industries, and scheduling and routing them in a conflict-free manner is crucial to their efficient operation. We propose a loop-based algorithm that solves the online, conflict-free scheduling and routing problem for AGVs with any capacity and ordered jobs in loop-based graphs. The proposed algorithm is compared against an exact method, a greedy heuristic and a metaheuristic. We experimentally show, using theoretical and real instances on a model representing a real manufacturing plant, that this algorithm either outperforms the other algorithms or gets an equally good solution in less computing time.