کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876134 | 689695 | 2014 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Set graphs. II. Complexity of set graph recognition and similar problems
ترجمه فارسی عنوان
تنظیم نمودار دوم پیچیدگی تشخیص گراف های مجموعه و مشکلات مشابه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Our approach in fact allows us to also show that the counting variants of the above problems are #P-complete, and prove similar complexity results for problems related to a generalization of extensional acyclic digraphs, the so-called hyper-extensional digraphs, which were proposed by Aczel to describe hypersets. Our proofs are based on reductions from variants of the Hamiltonian Path problem. We also consider a variant of the well-known notion of a separating code in a digraph, the so-called open-out-separating code, and show that it is NP-complete to determine whether an input extensional acyclic digraph contains an open-out-separating code of given size.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 547, 28 August 2014, Pages 70-81
Journal: Theoretical Computer Science - Volume 547, 28 August 2014, Pages 70-81
نویسندگان
Martin MilaniÄ, Romeo Rizzi, Alexandru I. Tomescu,