A Discrete Subexponential Algorithm for Parity Games

• We suggest a new randomized algorithm for solving Parity Games with the worst case time complexity roughlymin(O( n3 · ( n/k+1 )k),  2O(sqrt(nlog n))),where n is the number of vertices and k the number of colors of the game. Comparable with the previously known algorithms, which are efficient when the number of colors is small, it is subexponential when the number of colors is large, k = Omega (n1/2 + varepsilon). 

Subject headings

NATURVETENSKAP  -- Data- och informationsvetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences (hsv//eng)

Publication and Content Type

vet (subject category)

rap (subject category)