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

[img] PDF
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.
Item Type:Article
Copyright:© 2004 Elsevier
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 219739