ARRIVAL: Next Stop in CLS

DOI10.4230/LIPIcs.ICALP.2018.60zbMath1499.68144arXiv1802.07702OpenAlexW2962952142MaRDI QIDQ5002737

Pavel Hubáček, Hagar Mosaad, Thomas Dueholm Hansen, Karel Král, Veronika Slívová, Bernd Gärtner

Publication date: 28 July 2021

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

zbMATH Keywords

switch graphszero-player gameCLSUP \(n\) coup

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Randomized algorithms (68W20)

Related Items (7)

Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets ⋮ Unique end of potential line ⋮ The stochastic arrival problem ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ Reachability Switching Games ⋮ Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets ⋮ Unique End of Potential Line

Cites Work

• Did the train reach its destination: the complexity of finding a witness
• An algorithmic study of switch graphs
• Minimization algorithms and random walk on the d-cube
• How easy is local search?
• The complexity of stochastic games
• On the complexity of the parity argument and other inefficient proofs of existence
• Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
• ARRIVAL: A Zero-Player Graph Game in NP ∩ coNP
• Unnamed Item

This page was built for publication: ARRIVAL: Next Stop in CLS