Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871077 | Discrete Applied Mathematics | 2018 | 13 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Guillaume Fertin, Irena Rusu, Stéphane Vialette,