SAT and IP Based Algorithms for Magic Labeling with Applications

摘要

A labeling of a graph with n vertices and m edges is a one-to-one mapping from the union of the set of vertices and edges onto the set {1,2,..., m + n｝. Such a labeling is defined as magic, if one or both of the following two conditions is fulfilled: the sum of an edge label and the labels of its endpoint vertices is constant for all edges; the sum of a vertex label and the labels of its incident edges is constant for all vertices. We present effective IP and Sat based algorithms for the problem of finding a magic labeling for a given graph. We experimentally compare the resulted algorithms by applying it to random graphs. Finally, we demonstrate its performance by solving five open problems within the theory of magic graphs, posed in the book of Wallis.