Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
SAT and IP Based Algorithms for Magic Labeling with Applications
verfasst von : Gerold Jäger
Erschienen in: Combinatorial Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.