On variants of vertex geography on undirected graphs

DOI10.1016/j.dam.2018.05.044zbMath1440.05148OpenAlexW2809575668WikidataQ129621985 ScholiaQ129621985MaRDI QIDQ1627869

Blerina Sinaimeri, Angelo Monti

Publication date: 3 December 2018

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

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

zbMATH Keywords

computational complexityalgorithmic combinatorial game theoryshort winning strategy problemsundirected vertex geography

Mathematics Subject Classification ID

2-person games (91A05) Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

On the computational complexities of various geography variants

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding the winner in \(k\) rounds for DISJOINT ARROWS, a new combinatorial partizan game
• Matching theory
• Computing a perfect strategy for nxn chess requires time exponential in n
• Undirected edge geography
• Geography
• Complexity of path-forming games
• On the complexity of some two-person perfect-information games
• Heap games, numeration systems and sequences
• Combinatorial game theory foundations applied to digraph kernels
• Complexity, appeal and challenges of combinatorial games
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• The Shortest Path Game: Complexity and Algorithms
• N by N Checkers is Exptime Complete
• GO Is Polynomial-Space Hard
• Paths, Trees, and Flowers