17 citations · 38 across the 17 of their papers we have counts for
3 papers · 1 filter
Single-Player and Two-Player Buttons & Scissors Games
Kyle Burke, Erik D. Demaine, Harrison Gregg +12
We study the computational complexity of the Buttons \& Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-compl…
Circular Coloring of Random Graphs: Statistical Physics Investigation
Christian Schmidt, Nils-Eric Guenther, Lenka Zdeborová
Circular coloring is a constraints satisfaction problem where colors are assigned to nodes in a graph in such a way that every pair of connected nodes has two consecutive colors (t…
Computing Nonsimple Polygons of Minimum Perimeter
Sándor P. Fekete, Andreas Haas, Michael Hemmer +8
We provide exact and approximation methods for solving a geometric relaxation of the Traveling Salesman Problem (TSP) that occurs in curve reconstruction: for a given set of vertic…