کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952375 1364444 2017 27 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Directed hypergraphs: Introduction and fundamental algorithms-A survey
ترجمه فارسی عنوان
هیپرگراف های هدایت شده: مقدمه و الگوریتم های اساسی - یک نظرسنجی
کلمات کلیدی
هیپرگراس هدایت، بسته شدن گذرا، کاهش تدریجی، کوتاهترین پرتوها،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Just as ordinary hypergraphs are a generalization of graphs, directed hypergraphs (DH) are a natural generalization of digraphs. A DH consists of a set of vertices V and a set of hyperarcs H, where a hyperarc is a pair , S non empty subset of V and v∈V. DHs have a variety of applications: they have been used to represent functional dependency in databases, Horn formulae in propositional logic, and-or graphs, context free grammars etc. In the paper, after providing a brief historical introduction on the notion of DH and some relevant applications, various problems regarding DHs are surveyed and analyzed. In particular we consider the complexity of the reachability problem (together with its application in the related satisfiability problem for Horn CNF formulae) and the computation of transitive closure and transitive reduction of directed hypergraphs (together with its application to the computation of minimum coverings for a set of functional dependencies). Finally a short introduction to the problem of computing shortest hyperpaths in directed hypergraphs is provided.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 658, Part B, 7 January 2017, Pages 293-306
نویسندگان
, ,