کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6876002 690159 2016 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Graph operations on parity games and polynomial-time algorithms
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Graph operations on parity games and polynomial-time algorithms
چکیده انگلیسی
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
نویسندگان
, , ,