کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
13430959 | 1842442 | 2019 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the hydra number of disconnected graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On the hydra number of disconnected graphs On the hydra number of disconnected graphs](/preview/png/13430959.png)
چکیده انگلیسی
The hydra number is a new graph parameter related to some minimization problem for Horn formulas in propositional logic. The hydra number of a graph G=(V,E) is the smallest number of hyperarcs of the form uvâw in a directed hypergraph H=(V,F) such that if uvâE, then all vertices in V are reachable from {u,v} in H and if uvââE, then no other vertex apart from u and v is reachable from {u,v}. Reachability is defined by forward chaining, a standard marking procedure. In this paper we answer negatively a question posed in Sloan et al. (2017) concerning an anticipated formula for the hydra number of disconnected graphs. On the positive side, we show that the expression which appears in this formula is an upper bound for the hydra number of these graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 267, 31 August 2019, Pages 201-208
Journal: Discrete Applied Mathematics - Volume 267, 31 August 2019, Pages 201-208
نویسندگان
Angelika Nicgorska-MiÅkiewicz, MichaÅ TuczyÅski,