Clique-Width and Parity Games

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Kliková šířka a paritní hry
Autoři	OBDRŽÁLEK Jan
Rok publikování	2007
Druh	Článek ve sborníku
Konference	Computer Science Logic 2007, proceedings
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
Obor	Informatika
Klíčová slova	parity games; mu-calculus; clique-width
Popis	Otázka přesné složitosti řešení paritních her je jedním hlavních otevřených problémů ve verifikaci systémů, neboť je ekvivaletním problému ověřování modelu pro modální mu-kalkul. Známá horní hranice je NP a co-NP, ale není znám žádný polynomiální algoritmus. Bylo ukázáno, že na grafech podobných stromům (grafy s omezenou stromovou šířkou a DAG-šířkou) takový algoritmus existuje. Zde předkládáme polynomiální algoritmus pro paritní hry na grafech s omezenou klikovou šířkou (třída grafů obsahující například úplné bipartitiní grafy a kliky), čímž doplňujeme obrázek dané oblasti. Tento výsledek také rozšiřuje výsledek pro stromovou šířku, neboť grafy s omezenou stromovou šířkou mají i omezenou klikovou šířku. Algoritmus pracuje odlišně od svého protějšku pro omezenou stromovou šířku a značně využívá zajímavé vlastnosti paritních her.
Související projekty:	Institut Teoretické Informatiky