dc.contributor.author |
Bodlaender, H.L |
en |
dc.contributor.author |
Dinneen, Michael |
en |
dc.contributor.author |
Khoussainov, B |
en |
dc.date.accessioned |
2009-04-16T23:13:16Z |
en |
dc.date.available |
2009-04-16T23:13:16Z |
en |
dc.date.issued |
2001-04 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-151 (2001) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/3659 |
en |
dc.description.abstract |
In this paper, we study the complexity of deciding which player has a
winning strategy in certain types of McNaughton games. These graph games can be
used as models for computational problems and processes of infinite duration. We
consider the cases (1) where the first player wins when vertices in a specified set are
visited infinitely often and vertices in another specified set are visited finitely often, (2)
where the first player wins when exactly those vertices in one of a number of specified
disjoint sets are visited infinitely often, and (3) a generalization of these first two cases.
We give polynomial time algorithms to determine which player has a winning strategy
in each of the games considered. |
en |
dc.publisher |
Department of Computer Science, The University of Auckland, New Zealand |
en |
dc.relation.ispartofseries |
CDMTCS Research Report Series |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.source.uri |
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial |
en |
dc.title |
On Game-Theoretic Models of Networks |
en |
dc.type |
Technical Report |
en |
dc.subject.marsden |
Fields of Research::280000 Information, Computing and Communication Sciences |
en |
dc.rights.holder |
The author(s) |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |