.png){kind=icon}
Return
Algorithmic expedients for the S-labeling problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2019.04.014.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 vertical bar V vertical bar 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 5-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. (C) 2019 Elsevier Ltd. All rights reserved.
Keywords:
Graph labeling
Branch-and-cut
Lagrangian relaxation
Constraint programming
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W
Organization
Cited Papers
.png){kind=icon}
An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem
PREAI
ShareSaveShareSave
ShareSaveShareSavePSD-95 Is Essential for Hallucinogen and Atypical Antipsychotic Drug Actions at Serotonin ReceptorsOAAI
OAAIShareSaveShareSave
View more