کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871077 | 1440177 | 2018 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The S-labeling problem: An algorithmic tour
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The S-labeling problem: An algorithmic tour The S-labeling problem: An algorithmic tour](/preview/png/6871077.png)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 246, 10 September 2018, Pages 49-61
Journal: Discrete Applied Mathematics - Volume 246, 10 September 2018, Pages 49-61
نویسندگان
Guillaume Fertin, Irena Rusu, Stéphane Vialette,