Parallel Algorithms for Mean-Payoff Games: An Experimental Evaluation

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

CHALOUPKA Jakub

Year of publication 2009
Type Article in Proceedings
Conference Algorithms - European Symposium on Algorithms (ESA) 2009
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1007/978-3-642-04128-0_54
Field Informatics
Keywords mean-payoff games; parallel algorithms; experimental evaluation
Description Mean-payoff games (MPGs) have many applications, especially in the synthesis, analysis and verification of computer systems. Because of the size of these systems, there is a need to solve very large MPGs. Existing algorithms for solving MPGs are sequential, hence limited by the power of a single computer. In this paper, we propose several parallel algorithms based on the sequential ones. We also evaluate and compare the parallel algorithms experimentally.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.