[Zurück]

B. Klocker, G. Raidl:
"Heuristic Approaches for Finding Uniquely Hamiltonian Graphs of Minimum Degree Three with Small Crossing Numbers";
Vortrag: Austrian Workshop on Metaheuristics, Graz; 02.12.2016.

In graph theory, a prominent conjecture of Bondy and Jackson states that every uniquely hamiltonian planar graph must have a vertex of degree two. We formulate an optimization problem for constructing a uniquely hamiltonian graph and an embedding, such that the number of crossings of the embedding and the number of degree two vertices is minimal. For solving the problem we propose a general variable neighborhood search (GVNS). To check feasibility of neighbors we need to solve hamiltonian cycle problems, which is done in a delayed manner to minimize the computation effort. In the experiments we were able to find uniquely hamiltonian graphs with no degree two vertices and four crossings, but no planar graphs. Furthermore we will discuss a more general approach to solve similar con- struction problems or more generally bilevel optimization problems with an evolutionary algorithm. Many construction problems arising in graph theory have a bilevel structure in which the lower-level optimization problem is by it- self already NP-hard. Using an evolutionary algorithm we want to address a broad range of problems with a similar structure.