Algorithm for Two-Energy Games

Logo poskytovatele
Logo poskytovatele

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Název česky Algoritmus pro 2-Energy Games
Autoři

CHALOUPKA Jakub

Rok publikování 2010
Druh Článek ve sborníku
Konference Mathematical and Engineering Methods in Computer Science (MEMICS) 2010
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Obor Informatika
Klíčová slova energy games; games on k-dimensional vector addition systems with states; algorithm design
Popis A two-energy game (TEG) is a two-player game consisting of finite weighted directed graph and two unbounded counters. The weights of the edges are pairs from the set {-1, 0, 1}x{-1,0,1}. The two players, named Box and Diamond, move a token along the edges of the graph ad infinitum, and the weight of each traversed edge is added to the two counters. Box's aim is to keep both counters non-negative, while Diamond wants to make at least one of the counters go below zero. TEGs have applications in resource scheduling, and it has been recently shown (Chaloupka, 2010) that deciding the winner in two-energy games is in the complexity class P. This encourages searching for efficient algorithms for TEGs. In this paper, we design a novel algorithm for TEGs and evaluate it in a preliminary experimental study.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.