کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
13431269 | 1842497 | 2020 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Algorithm and hardness results on hop domination in graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Algorithm and hardness results on hop domination in graphs Algorithm and hardness results on hop domination in graphs](/preview/png/13431269.png)
چکیده انگلیسی
Two vertices in a graph are said to 2-step dominate each other if they are at distance 2 apart. A set S of vertices in a graph G=(V,E) is a hop dominating set of G if every vertex outside S is 2-step dominated by some vertex of S. Given a graph G, Min-HDS is the problem of finding a hop dominating set of G of minimum cardinality. The decision version of Min-HDS is known to be NP-complete for planar bipartite graphs and planar chordal graphs, and hence for bipartite graphs and chordal graphs. In this paper, we present a linear time algorithm for computing a minimum hop dominating set in bipartite permutation graphs, which is a subclass of bipartite graphs. We also show that Min-HDS cannot be approximated within a factor of (1âε)lnâ¡|V|, unless P=NP and can be approximated within a factor of 1+lnâ¡(Î(Îâ1)+1), where Î denotes the maximum degree in the graph G. Finally, we show that Min-HDS is APX-complete for bipartite graphs of maximum degree 3.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 153, January 2020, 105872
Journal: Information Processing Letters - Volume 153, January 2020, 105872
نویسندگان
Michael A. Henning, Saikat Pal, D. Pradhan,