On Streaming Algorithms for the Steiner Cycle and Path Cover Problem on Interval Graphs and Falling Platforms in Video Games

Ante Ćustić, Stefan Lendl

We introduce a simplified model for platform game levels with falling platforms based on interval graphs and show that solvability of such levels corresponds to finding Steiner cyc…