An O(n^2) Time Algorithm for Alternating Büchi Games

Details An O(n^2) Time Algorithm for Alternating Büchi Games An O(n^2) Time Algorithm for Alternating Büchi Games

2011-09-23

arxiv.org/abs/1109.5018v1

Computer Science

Computer Science and Game Theory

Scientific paper

Computing the winning set for B{\"u}chi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is $\tilde{O}(n \cdot m)$, where $n$ is the number of vertices and $m$ is the number of edges in the graph. We are the first to break the $\tilde{O}(n\cdot m)$ bound by presenting a new technique that reduces the running time to $O(n^2)$. This bound also leads to an $O(n^2)$ algorithm time for computing the set of almost-sure winning vertices in alternating games with probabilistic transitions (improving an earlier bound of $\tilde{O}(n\cdot m)$) and in concurrent graph games with constant actions (improving an earlier bound of $O(n^3)$). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time $O(n^2)$. Finally, we show how to maintain the winning set for B{\"u}chi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem.

Affiliated with

Also associated with

No associations

Rating

An O(n^2) Time Algorithm for Alternating Büchi Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An O(n^2) Time Algorithm for Alternating Büchi Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An O(n^2) Time Algorithm for Alternating Büchi Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-724155