کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874233 | 1441031 | 2018 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Recognizing Union-Find trees is NP-complete
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Disjoint-Set forests, consisting of Union-Find trees, are data structures having a widespread practical application due to their efficiency. Despite them being fundamental, no exact structural characterization of these trees is known (such a characterization exists for Union trees which are constructed without using path compression). In this paper we provide such a characterization by means of a simple operation and we show that the problem of deciding whether a given tree is a Union-Find tree is NP-complete.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 131, March 2018, Pages 7-14
Journal: Information Processing Letters - Volume 131, March 2018, Pages 7-14
نویسندگان
Kitti Gelle, Szabolcs Iván,