It is tough to be a plumber

Daniel Král, Vladan Majerech, Jirí Sgall, Tomass Tichy, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)
1 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)474-484
Number of pages10
JournalTheoretical computer science
Volume313
Issue number3
DOIs
Publication statusPublished - 2004

Keywords

  • Combinatorial game theory
  • METIS-219739
  • IR-76286
  • NP-completeness

Fingerprint

Dive into the research topics of 'It is tough to be a plumber'. Together they form a unique fingerprint.

Cite this