کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875496 | 1441959 | 2018 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Convex and isometric domination of (weak) dominating pair graphs
ترجمه فارسی عنوان
تسلط کنسرو و ایزومتریک نمودارهای جفت (ضعیف) غالب
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تسلط قوسی، غالب نمودار جفتی، سلطه ایزومتریک، پوست کنده
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A set D of vertices in a graph G is a dominating set if every vertex of G, which is not in D, has a neighbor in D. A set of vertices D in G is convex (respectively, isometric), if all vertices in all shortest paths (respectively, all vertices in one of the shortest paths) between any two vertices in D lie in D. The problem of finding a minimum convex dominating (respectively, isometric dominating) set is considered in this paper from algorithmic point of view. For the class of weak dominating pair graphs (i.e., the graphs that contain a dominating pair, which is a pair of vertices x,yâV(G) such that vertices of any path between x and y form a dominating set), we present an efficient algorithm that finds a minimum isometric dominating set of such a graph. On the other hand, we prove that even if one restricts to weak dominating pair graphs that are also chordal graphs, the problem of deciding whether there exists a convex dominating set bounded by a given arbitrary positive integer is NP-complete. By further restricting the class of graphs to chordal dominating pair graphs (i.e., the chordal graphs in which every connected induced subgraph has a dominating pair) we are able to find a polynomial time algorithm that determines the minimum size of a convex dominating set of such a graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 730, 19 June 2018, Pages 32-43
Journal: Theoretical Computer Science - Volume 730, 19 June 2018, Pages 32-43
نویسندگان
Boštjan Brešar, Tanja Gologranc, Tim Kos,