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

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
نویسندگان
, , , , ,