It is tough to be a plumber

Share/Save/Bookmark

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

[img] PDF
Restricted to UT campus only
: Request a copy
215kB
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.
Item Type:Article
Copyright:© 2004 Elsevier
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/76286
Official URL:http://dx.doi.org/10.1016/j.tcs.2002.12.002
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 219739