- No file added yet -

# Algorithms for Büchi Games

conference contribution

posted on 2015-10-21, 10:59 authored by K. Chatterjee, Thomas A. Henzinger, Nir PitermanThe classical algorithm for solving B\"uchi games requires time $O(n\cdot m)$ for game graphs with $n$ states and $m$ edges. For game graphs with constant outdegree, the best known algorithm has running time $O(n^2/\log n)$. We present two new algorithms for B\"uchi games. First, we give an algorithm that performs at most $O(m)$ more work than the classical algorithm, but runs in time O(n) on infinitely many graphs of constant outdegree on which the classical algorithm requires time $O(n^2)$. Second, we give an algorithm with running time $O(n\cdot m\cdot\log\delta(n)/\log n)$, where $1\le\delta(n)\le n$ is the outdegree of the game graph. Note that this algorithm performs asymptotically better than the classical algorithm if $\delta(n)=O(\log n)$.

## History

## Citation

arXiv:0805.2620v1 Computer Science and Game Theory 2008## Author affiliation

/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Science## Version

- AM (Accepted Manuscript)

## Published in

arXiv:0805.2620v1 Computer Science and Game Theory 2008## Copyright date

2008## Available date

2015-10-21## Publisher version

http://arxiv.org/abs/0805.2620v1## Notes

11 Pages, Published in GDV 06 (Games in Design and Verification)## Language

en## Administrator link

## Usage metrics

## Categories

No categories selected## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC