GAJARSKÝ, Jakub, Sebastian ORDYNIAK, Michael LAMPIS, Valia MITSOU a Kazuhisa MAKINO. Parameterized Algorithms for Parity Games. In Italiano, Giuseppe F. , Pighizzini, Giovanni, Sannella, Donald T. MFCS 2015, LNCS 9235. 9235. vyd. Berlin: Springer. s. 336-347. ISBN 978-3-662-48053-3. doi:10.1007/978-3-662-48054-0_28. 2015.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Parameterized Algorithms for Parity Games
Autoři GAJARSKÝ, Jakub (703 Slovensko, garant, domácí), Sebastian ORDYNIAK (276 Německo), Michael LAMPIS (300 Řecko), Valia MITSOU (300 Řecko) a Kazuhisa MAKINO (392 Japonsko).
Vydání 9235. vyd. Berlin, MFCS 2015, LNCS 9235, od s. 336-347, 12 s. 2015.
Nakladatel Springer
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 10201 Computer sciences, information science, bioinformatics
Stát vydavatele Německo
Utajení není předmětem státního či obchodního tajemství
Forma vydání elektronická verze "online"
Impakt faktor Impact factor: 0.402 v roce 2005
Kód RIV RIV/00216224:14330/15:00081184
Organizační jednotka Fakulta informatiky
ISBN 978-3-662-48053-3
ISSN 0302-9743
Doi http://dx.doi.org/10.1007/978-3-662-48054-0_28
UT WoS 000371027300028
Klíčová slova anglicky parity games; model checking; modular-width
Štítky core_A, firank_A
Změnil Změnil: RNDr. Pavel Šmerk, Ph.D., učo 3880. Změněno: 28. 4. 2016 15:11.
Anotace
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.
Návaznosti
GBP202/12/G061, projekt VaVNázev: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)
Investor: Grantová agentura ČR, Centrum excelence - Institut teoretické informatiky
MUNI/A/1159/2014, interní kód MUNázev: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IV.
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IV., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/1206/2014, interní kód MUNázev: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Akronym: SKOMU)
Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
VytisknoutZobrazeno: 28. 3. 2024 23:17