Name
Abstract | ||
|---|---|---|
We suggest a new randomized algorithm for solving parity games with worst case time complexity roughly min(O(n3 驴 (n/k+ 1)k), 2O(驴n log n), where n is the number of vertices and k the number of colors of the game. This is comparable with the previously known algorithms when the number of colors is small. However, the subexponential bound is an advantage when the number of colors is large, k = 驴(n1/2+驴). |
Year | Venue | Keywords |
|---|---|---|
2003 | STACS | parity game,new randomized algorithm,parity games,n log n,worst case time complexity,discrete subexponential algorithm,randomized algorithm,time complexity |
Field | DocType | Volume |
Randomized algorithm,Discrete mathematics,Combinatorics,Vertex (geometry),Bipartite graph,Algorithm,Directed graph,Tree automaton,Parity (mathematics),Time complexity,Mathematics | Conference | 2607 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-00623-0 | 29 |
PageRank | References | Authors |
1.83 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Henrik Björklund | 1 | 311 | 20.41 |
| Sven Sandberg | 2 | 140 | 9.64 |
| Sergei G. Vorobyov | 3 | 92 | 7.40 |