WFRF:(Sandberg Henrik)
Sökning: WFRF:(Sandberg Henrik) > (2000-2004) > 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
- Rapport (övrigt vetenskapligt/konstnärligt)
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)
Till lärosätets databas
Hitta mer i SwePub
- Av författaren/redakt...
- Björklund, Henri ...
- Sandberg, Sven
- Vorobyov, Sergei
- Om ämnet
-
- NATURVETENSKAP
- NATURVETENSKAP
- och Data och informa ...
- Delar i serien
- Technical report ...
- Av lärosätet
- Uppsala universitet
Sök utanför SwePub
- Sök vidare i:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - Nationella bibliotekssystem
- LIBRIS.kb.se
