On the shortest path game

DOI10.1016/j.dam.2015.08.003zbMath1351.05152OpenAlexW2164315917WikidataQ61638296 ScholiaQ61638296MaRDI QIDQ729795

Joachim Schauer, Ulrich Pferschy, Andreas Darmann

Publication date: 22 December 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.08.003

zbMATH Keywords

computational complexitygame theoryshortest path problemcactus graph

Mathematics Subject Classification ID

2-person games (91A05) Games involving graphs (91A43) Paths and cycles (05C38) Distance in graphs (05C12) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

The shortest connection game, Competitive multi-agent scheduling with an iterative selection rule

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Subset Sum game
• PSPACE-Hardness of some combinatorial games
• Undirected edge geography
• Geography
• Complexity of path-forming games
• On the complexity of some two-person perfect-information games
• Bounded-width QBF is PSPACE-complete
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
• The Shortest Path Game: Complexity and Algorithms
• GO Is Polynomial-Space Hard
• Algorithmic Game Theory