It is tough to be a plumber

DOI10.1016/j.tcs.2002.12.002zbMath1066.91020OpenAlexW2135480548WikidataQ57601589 ScholiaQ57601589MaRDI QIDQ1885007

Vladan Majerech, Jiří Sgall, Daniel Král', Tomas Tichý, Gerhard J. Woeginger

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2002.12.002

zbMATH Keywords

NP-completenessCombinatorial game theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial games (91A46)

Related Items

Tetravex is NP-complete

Cites Work

• Matching theory
• A special planar satisfiability problem and a consequence of its NP- completeness
• Planar Formulae and Their Uses
• Determining the thickness of graphs is NP-hard
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Unnamed Item
• Unnamed Item