کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435773 | 689934 | 2015 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Computing the Tutte polynomial of lattice path matroids using determinantal circuits
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We give a quantum-inspired O(n4)O(n4) algorithm computing the Tutte polynomial of a lattice path matroid, where n is the size of the ground set of the matroid. Furthermore, this can be improved to O(n2)O(n2) arithmetic operations if we evaluate the Tutte polynomial on a given input, fixing the values of the variables. The best existing algorithm, found in 2004, was O(n5)O(n5), and the problem has only been known to be polynomial time since 2003. Conceptually, our algorithm embeds the computation in a determinant using a recently demonstrated equivalence of categories useful for counting problems such as those that appear in simulating quantum systems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 598, 20 September 2015, Pages 150–156
Journal: Theoretical Computer Science - Volume 598, 20 September 2015, Pages 150–156
نویسندگان
Jason Morton, Jacob Turner,