Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1316738, author = {Gajarský, Jakub and Ordyniak, Sebastian and Lampis, Michael and Mitsou, Valia and Makino, Kazuhisa}, address = {Berlin}, booktitle = {MFCS 2015, LNCS 9235}, doi = {http://dx.doi.org/10.1007/978-3-662-48054-0_28}, edition = {9235}, editor = {Italiano, Giuseppe F. , Pighizzini, Giovanni, Sannella, Donald T.}, keywords = {parity games; model checking; modular-width}, howpublished = {elektronická verze "online"}, language = {eng}, location = {Berlin}, isbn = {978-3-662-48053-3}, pages = {336-347}, publisher = {Springer}, title = {Parameterized Algorithms for Parity Games}, year = {2015} }
TY - JOUR ID - 1316738 AU - Gajarský, Jakub - Ordyniak, Sebastian - Lampis, Michael - Mitsou, Valia - Makino, Kazuhisa PY - 2015 TI - Parameterized Algorithms for Parity Games PB - Springer CY - Berlin SN - 9783662480533 KW - parity games KW - model checking KW - modular-width N2 - Determining the winner of a Parity Game is a major problem in computational complexity with a number of applications in verification. In a parameterized complexity setting, the problem has often been considered with parameters such as (directed versions of) treewidth or clique-width, by applying dynamic programming techniques. In this paper we adopt a parameterized approach which is more inspired by well-known (non-parameterized) algorithms for this problem. We consider a number of natural parameterizations, such as by Directed Feedback Vertex Set, Distance to Tournament, and Modular Width. We show that, for these parameters, it is possible to obtain recursive parameterized algorithms which are simpler, faster and only require polynomial space. We complement these results with some algorithmic lower bounds which, among others, rule out a possible avenue for improving the best-known sub-exponential time algorithm for parity games. ER -
GAJARSKÝ, Jakub, Sebastian ORDYNIAK, Michael LAMPIS, Valia MITSOU and Kazuhisa MAKINO. Parameterized Algorithms for Parity Games. Online. In Italiano, Giuseppe F. , Pighizzini, Giovanni, Sannella, Donald T. \textit{MFCS 2015, LNCS 9235}. 9235th ed. Berlin: Springer, 2015, p.~336-347. ISBN~978-3-662-48053-3. Available from: https://dx.doi.org/10.1007/978-3-662-48054-0\_{}28.
|