کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876002 | 690159 | 2016 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Graph operations on parity games and polynomial-time algorithms
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper we establish polynomial-time algorithms for special classes of parity games. In particular we study various constructions for combining graphs that often arise in structural graph theory and show that polynomial-time solvability of parity games is preserved under these operations. This includes the join of two graphs, repeated pasting along vertices, and the addition of a vertex. As a consequence we obtain polynomial time algorithms for parity games whose underlying graph is an orientation of a complete graph (such as tournaments), a complete bipartite graph, a block graph, or a block-cactus graph. These are classes where the problem was not known to be efficiently solvable before.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 614, 8 February 2016, Pages 97-108
Journal: Theoretical Computer Science - Volume 614, 8 February 2016, Pages 97-108
نویسندگان
Christoph Dittmann, Stephan Kreutzer, Alexandru I. Tomescu,