Sökning: onr:"swepub:oai:DiVA.org:uu-45450" >
A Discrete Subexpon...
A Discrete Subexponential Algorithm for Parity Games
-
- Björklund, Henrik (författare)
- Uppsala universitet,Institutionen för informationsteknologi,Datalogi,Computing science
-
- Sandberg, Sven (författare)
- Uppsala universitet,Institutionen för informationsteknologi,Datalogi,Computing science
-
- Vorobyov, Sergei (författare)
- Uppsala universitet,Institutionen för informationsteknologi,Datalogi,Computing science
-
(creator_code:org_t)
- 2002
- Engelska.
-
Serie: Technical report / Department of Information Technology, Uppsala University, 1404-3203 ; 2002-026
- Relaterad länk:
-
https://uu.diva-port... (primary) (Raw object)
-
visa fler...
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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).
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Publikations- och innehållstyp
- vet (ämneskategori)
- rap (ämneskategori)