کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875646 1441978 2018 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A QPTAS for the base of the number of crossing-free structures on a planar point set
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A QPTAS for the base of the number of crossing-free structures on a planar point set
چکیده انگلیسی
The number of triangulations of a planar n point set S is known to be cn, where the base c lies between 2.43 and 30. Similarly, the number of crossing-free spanning trees on S is known to be dn, where the base d lies between 6.75 and 141.07. The fastest known algorithm for counting triangulations of S runs in 2(1+o(1))nlog⁡n time while that for counting crossing-free spanning trees runs in O⁎(7.125n) time. The fastest known, non-trivial approximation algorithms for the number of triangulations of S and the number of crossing-free spanning trees of S, respectively, run in time subexponential in n. We present the first non-trivial approximation algorithms for these numbers running in quasi-polynomial time. They yield the first quasi-polynomial approximation schemes for the base of the number of triangulations of S and the base of the number of crossing-free spanning trees on S, respectively.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 711, 8 February 2018, Pages 56-65
نویسندگان
, , ,