It is tough to be a plumber

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

doi:10.1016/j.tcs.2002.12.002

It is tough to be a plumber

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

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-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 language	English
Pages (from-to)	474-484
Number of pages	10
Journal	Theoretical computer science
Volume	313
Issue number	3
DOIs	https://doi.org/10.1016/j.tcs.2002.12.002
Publication status	Published - 2004

Keywords

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

Access to Document

10.1016/j.tcs.2002.12.002

Cite this

@article{3bcbf2f07eeb4d89a2a2fb2dc5d30455,

title = "It is tough to be a plumber",

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.",

keywords = "Combinatorial game theory, METIS-219739, IR-76286, NP-completeness",

author = "Daniel Kr{\'a}l and Vladan Majerech and Jir{\'i} Sgall and Tomass Tichy and Gerhard Woeginger",

year = "2004",

doi = "10.1016/j.tcs.2002.12.002",

language = "English",

volume = "313",

pages = "474--484",

journal = "Theoretical computer science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - It is tough to be a plumber

AU - Král, Daniel

AU - Majerech, Vladan

AU - Sgall, Jirí

AU - Tichy, Tomass

AU - Woeginger, Gerhard

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

KW - Combinatorial game theory

KW - METIS-219739

KW - IR-76286

KW - NP-completeness

U2 - 10.1016/j.tcs.2002.12.002

DO - 10.1016/j.tcs.2002.12.002

M3 - Article

SN - 0304-3975

VL - 313

SP - 474

EP - 484

JO - Theoretical computer science

JF - Theoretical computer science

IS - 3

ER -

It is tough to be a plumber

Abstract

Keywords

Access to Document

Fingerprint

Cite this