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

PDF
Restricted to UT campus only: Request a copy
210Kb

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:	Discrete Mathematics and Mathematical Programming (DMMP)
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

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 219739