The S-labeling problem: An algorithmic tour

Given a graph G=(V,E) of order n and maximum degree Δ, the NP-complete S-labeling problem consists in finding a labeling of G, i.e. a bijective mapping ϕ:V→{1,2…n}, such that SLϕ(G)=∑uv∈Emin{ϕ(u),ϕ(v)} is minimized. In this paper, we study the S-labeling problem, with a particular focus on algorithm...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2018-09, Vol.246, p.49-61
Main Authors: Fertin, Guillaume, Rusu, Irena, Vialette, Stéphane
Format: Article
Language:English
Subjects:
Algorithm
Applied mathematics
Caterpillars
Computer Science
Data Structures and Algorithms
Graph algorithms
Graph labeling
Graphs
Greedy algorithms
Labeling
Lower bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a graph G=(V,E) of order n and maximum degree Δ, the NP-complete S-labeling problem consists in finding a labeling of G, i.e. a bijective mapping ϕ:V→{1,2…n}, such that SLϕ(G)=∑uv∈Emin{ϕ(u),ϕ(v)} is minimized. In this paper, we study the S-labeling problem, with a particular focus on algorithmic issues. We first give intrinsic properties of optimal labelings, which will prove useful for our algorithmic study. We then provide lower bounds on SLϕ(G), together with a generic greedy algorithm, which collectively allow us to approximate the problem in several classes of graphs—in particular, we obtain constant approximation ratios for regular graphs and bounded degree graphs. We also show that deciding whether there exists a labeling ϕ of G such that SLϕ(G)≤|E|+k is solvable in O∗(22k(2k)!) time, thus fixed-parameterized tractable in k. We finally show that the S-Labeling problem is polynomial-time solvable for two classes of graphs, namely split graphs and (sets of) caterpillars.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2017.07.036