B. Klocker, H. Fleischner, G. Raidl:

"Finding Uniquely Hamiltonian Graphs of Minimum Degree Three with Small Crossing Numbers";

Talk: International Workshop on Hybrid Metaheuristics (HM), Plymouth, United Kingdom; 2016-06-08 - 2016-06-10; in: "Hybrid Metaheuristics - 10th International Workshop on Hybrid Metaheuristics", LNCS, 9668 (2016), ISBN: 978-3-319-39635-4; 87 - 103.

In graph theory, a prominent conjecture of Bondy and Jackson states that every uniquely hamiltonian planar graph must have a vertex of degree two. In this work we try to find uniquely hamiltonian graphs with minimum degree three and a small crossing number by minimizing the number of crossings in an embedding and the number of degree-two vertices. We formalize an optimization problem for this purpose and propose a general variable neighborhood search (GVNS) for solving it heuristically. The several different types of used neighborhoods also include an exponentially large neighborhood that is effectively searched by means of branch and bound. To check feasibility of neighbors we need to solve hamiltonian cycle problems, which is done in a delayed manner to minimize the computation effort. We compare three different configurations of the GVNS. Although our implementation could not find a uniquely hamiltonian planar graph with minimum degree three disproving Bondy and Jacksonīs conjecture, we were able to find uniquely hamiltonian graphs of minimum degree three with crossing number four for all number of vertices from 10 to 100.

http://dx.doi.org/10.1007/978-3-319-39636-1

http://publik.tuwien.ac.at/files/publik_256525.pdf

Created from the Publication Database of the Vienna University of Technology.