Polynomial-time algorithms for energy games with special weight structures

DOI10.1007/s00453-013-9843-7zbMath1303.91048arXiv1604.08234MaRDI QIDQ487011

Krishnendu Chatterjee, Sebastian Krinninger, Danupon Nanongkai, Monika R. Henzinger

Publication date: 19 January 2015

Published in: Algorithmica, Algorithms – ESA 2012 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.08234

zbMATH Keywords

graph algorithms; polynomial-time algorithms; energy games; mean-payoff games; turn-based infinite duration games

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

91A05: 2-person games

91A43: Games involving graphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms