Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
DOI10.1016/J.TCS.2020.05.031zbMATH Open1453.68087OpenAlexW3037560582MaRDI QIDQ2196563FDOQ2196563
Authors: Jeffrey Bosboom, Michael J. Coulombe, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, Mikhail Rudoy, Clemens Thielen, Zachary R. Abel
Publication date: 3 September 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1721.1/128888
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Games involving graphs (91A43)
Cites Work
- Title not available (Why is that?)
- The Problem of Compatible Representatives
- Hamilton Paths in Grid Graphs
- Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
- The undecidability of the domino problem
- Constructing Arrangements of Lines and Hyperplanes with Applications
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Title not available (Why is that?)
- Drawing graphs on rectangular grids
- The Complexity of Planar Counting Problems
- Title not available (Why is that?)
- Send-and-Split Method for Minimum-Concave-Cost Network Flows
- On Steiner’s Problem with Rectilinear Distance
- Classic Nintendo games are (computationally) hard
- On the complexity of deadlock detection in families of planar nets
- Fun with fonts: algorithmic typography
- Edge-matching problems with rotations
- Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
- Title not available (Why is that?)
This page was built for publication: Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196563)