کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333172 | 688607 | 2009 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Algorithms for generating convex sets in acyclic digraphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A set X of vertices of an acyclic digraph D is convex if Xâ â
and there is no directed path between vertices of X which contains a vertex not in X. A set X is connected if Xâ â
and the underlying undirected graph of the subgraph of D induced by X is connected. Connected convex sets and convex sets of acyclic digraphs are of interest in the area of modern embedded processor technology. We construct an algorithm A for enumeration of all connected convex sets of an acyclic digraph D of order n. The time complexity of A is O(nâ
cc(D)), where cc(D) is the number of connected convex sets in D. We also give an optimal algorithm for enumeration of all (not just connected) convex sets of an acyclic digraph D of order n. In computational experiments we demonstrate that our algorithms outperform the best algorithms in the literature.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 7, Issue 4, December 2009, Pages 509-518
Journal: Journal of Discrete Algorithms - Volume 7, Issue 4, December 2009, Pages 509-518
نویسندگان
P. Balister, S. Gerke, G. Gutin, A. Johnstone, J. Reddington, E. Scott, A. Soleimanfallah, A. Yeo,