It is tough to be a plumber
Král, Daniel and Majerech, Vladan and Sgall, Jiií and Tichy, Tomass and Woeginger, Gerhard (2004) It is tough to be a plumber. Theoretical Computer Science, 313 (3). pp. 473-484. ISSN 0304-3975
Restricted to UT campus only : Request a copy
|Abstract:||In the Linux computer game KPlumber, the objective is to rotate tiles in a raster of squares so as to complete a system of pipes. We give a complexity classification for the original game and various special cases of it that arise from restricting the set of six possible tiles.
Most of the cases are NP-complete. One polynomially solvable case is settled by formulating it as a perfect matching problem; other polynomial cases are settled by simple sweepline techniques. Moreover, we show that all the unsettled cases are polynomial time equivalent.
|Copyright:||© 2004 Elsevier|
Electrical Engineering, Mathematics and Computer Science (EEMCS)
|Link to this item:||http://purl.utwente.nl/publications/76286|
|Export this item as:||BibTeX|
Daily downloads in the past month
Monthly downloads in the past 12 months
Repository Staff Only: item control page
Metis ID: 219739