کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418845 | 681722 | 2015 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph](/preview/png/418845.png)
چکیده انگلیسی
Baker and Norine introduced a graph-theoretic analogue of the Riemann–Roch theory. A central notion in this theory is the rank of a divisor. In this paper we prove that computing the rank of a divisor on a graph is NP-hard, even for simple graphs.The determination of the rank of a divisor can be translated to a question about a chip-firing game on the same underlying graph. We prove the NP-hardness of this question by relating chip-firing on directed and undirected graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 193, 1 October 2015, Pages 48–56
Journal: Discrete Applied Mathematics - Volume 193, 1 October 2015, Pages 48–56
نویسندگان
Viktor Kiss, Lilla Tóthmérész,