کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430580 | 688051 | 2012 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An algorithm for finding input–output constrained convex sets in an acyclic digraph
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A set X of vertices of an acyclic graph is convex if any vertex on a directed walk between elements of X is itself in X. We construct an algorithm for generating all input–output constrained convex (IOCC) sets in an acyclic digraph, which uses several novel ideas. We show that the time complexity of our algorithm significantly improves the best one known from the literature. IOCC sets of acyclic digraphs are of interest in the area of modern embedded processor technology.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 13, May 2012, Pages 47–58
Journal: Journal of Discrete Algorithms - Volume 13, May 2012, Pages 47–58
نویسندگان
G. Gutin, A. Johnstone, J. Reddington, E. Scott, A. Yeo,