کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950652 1364296 2017 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
CNF and DNF succinct graph encodings
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
CNF and DNF succinct graph encodings
چکیده انگلیسی
We also study the complexity of the succinct versions of the Graph Isomorphism problem. We show that all the versions are hard for PSPACE. Although the exact complexity of these problems is still unknown, we show that under most existing succinct models the different versions of the problem are equivalent. We also give an algorithm for the DNF encoded version of GI whose running time depends mainly on the number of terms in the succinct representation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 253, Part 3, April 2017, Pages 436-447
نویسندگان
, , ,