Clique-Width and Parity Games
| Název česky | Kliková šířka a paritní hry |
|---|---|
| Autoři | |
| Rok publikování | 2007 |
| Druh | Článek ve sborníku |
| Konference | Computer Science Logic 2007, proceedings |
| Fakulta / Pracoviště MU | |
| 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: |