umu.sePublications
Change search

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
SAT and IP Based Algorithms for Magic Labeling Including a Complete Search for Total Magic Labelings
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
(Formal Methods & Tools Group, Department of Computer Science, University of Twente, The Nnetherlands)
2015 (English)In: Journal of Discrete Algorithms, ISSN 1570-8667, E-ISSN 1570-8675, Vol. 31, p. 87-103Article in journal (Refereed) Published
##### Abstract [en]

In this paper 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. If a graph has a labeling fulfilling both conditions, it is called a totally magic graph. We present effective IP and Sat based algorithms for the problem of finding a magic labeling for a given graph, and we extend these algorithms also to find all magic labelings for a given graph. We experimentally compare the resulted algorithms by applying it to random graphs. Finally, we demonstrate its performance by solving small cases of seven open problems within the theory of magic graphs. As main practical result we perform an exhaustive search showing that no totally magic graph with 11 vertices exists.

##### Place, publisher, year, edition, pages
2015. Vol. 31, p. 87-103
##### Keywords [en]
Boolean satisfiability, Integer programming, Magic labeling
##### National Category
Discrete Mathematics
##### Identifiers
ISI: 000358518400008OAI: oai:DiVA.org:umu-100105DiVA, id: diva2:790211
Available from: 2015-02-23 Created: 2015-02-23 Last updated: 2018-06-07Bibliographically approved

#### Open Access in DiVA

No full text in DiVA

Publisher's full text

Jäger, Gerold

#### Search in DiVA

Jäger, Gerold
##### By organisation
Department of Mathematics and Mathematical Statistics
##### In the same journal
Journal of Discrete Algorithms
##### On the subject
Discrete Mathematics

doi
urn-nbn

#### Altmetric score

doi
urn-nbn
Total: 200 hits

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf