  Graph labeling problems have been widely studied in the last decades and have
a vast area of application. In this work, we study the recently introduced
S-labeling problem, in which the nodes get labeled using labels from 1 to |V |
and for each edge the contribution to the objective function, called S-labeling
number of the graph, is the minimum label of its end-nodes. The goal is to find
a labeling with minimum value. The problem is NP-hard for planar subcubic
graphs, although for many other graph classes the complexity status is still
unknown. In this paper, we present different algorithmic approaches for
tackling this problem: We develop an exact solution framework based on
Mixed-Integer Programming (MIP) which is enhanced with valid inequalities,
starting and primal heuristics and specialized branching rules. We show that
our MIP formulation has no integrality gap for paths, cycles and perfect n-ary
trees, and, to the best of our knowledge, we give the first polynomial-time
algorithm for the problem on n-ary trees as well as a closed formula for the
S-labeling number for such trees. Moreover, we also present a Lagrangian
heuristic and a constraint programming approach. A computational study is
carried out in order to (i) investigate if there may be other special graph
classes, where our MIP formulation has no integrality gap, and (ii) assess the
effectiveness of the proposed solution approaches for solving the problem on a
dataset consisting of general graphs.
