---
res:
bibo_abstract:
- The classical algorithm for solving Bu ̈chi games requires time O(n · m) for game
graphs with n states and m edges. For game graphs with constant outdegree, the
best known algorithm has running time O(n2/logn). We present two new algorithms
for Bu ̈chi 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(n2). Second,
we give an algorithm with running time O(n · m · log δ(n)/ log n), where 1 ≤ δ(n)
≤ n is the outdegree of the game graph. Note that this algorithm performs asymptotically
better than the classical algorithm if δ(n) = O(log n).@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Krishnendu Chatterjee
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Thomas A
foaf_name: Thomas Henzinger
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87
orcid: 0000−0002−2985−7724
- foaf_Person:
foaf_givenName: Nir
foaf_name: Piterman, Nir
foaf_surname: Piterman
dct_date: 2006^xs_gYear
dct_publisher: ACM@
dct_title: Algorithms for Büchi Games@
...