کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951926 | 1441995 | 2017 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Dominator sequences in bipartite graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Let G=(V,E) be a bipartite graph with bipartition X,Y and let |X|â¤|Y|. A dominator sequence in G is a sequence of vertices (x1,x2,â¦,xk) in X such that for each i with 2â¤iâ¤k, vertex xi dominates at least one vertex in Y which is not dominated by x1,x2,â¦,xiâ1. The maximum length of a dominator sequence in G is called the dominator sequence number of G and is denoted by â(G). In this paper we present several basic results on this parameter. We prove that the decision problem for the parameter â(G) is NP-Complete. We obtain bounds for â(G) and discuss applications in the study of optical networks.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 694, 19 September 2017, Pages 34-41
Journal: Theoretical Computer Science - Volume 694, 19 September 2017, Pages 34-41
نویسندگان
B. Jayaram, S. Arumugam, K. Thulasiraman,