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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.