Unweighted Layered Graph Traversal: Passing a Crown via Entropy Maximization

Xingjian Bai, Christian Coester, Romain Cosson

Introduced by Papadimitriou and Yannakakis in 1989, layered graph traversal is a central problem in online algorithms and mobile computing that has been studied for several decades…