3 citations · 5 across the 6 of their papers we have counts for
6 papers
NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
Chao Yang, Zhujun Zhang
The computational complexity of tiling finite simply connected regions with a fixed set of tiles is studied in this paper. We show that the problem of tiling simply connected regio…
Undecidability of tiling the plane with a fixed number of Wang bars
Chao Yang, Zhujun Zhang
To study the fixed parameter undecidability of tiling problem for a set of Wang tiles, Jeandel and Rolin show that the tiling problem for a set of 44 Wang bars is undecidable. In t…
A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of polyominoes
Chao Yang, Zhujun Zhang
We give a proof of Ollinger's conjecture that the problem of tiling the plane with translated copies of a set of polyominoes is undecidable. The techniques employed in our proo…
Atropos-k is PSPACE-complete
Chao Yang, Zhujun Zhang
Burke and Teng introduced a two-player combinatorial game Atropos based on Sperner's lemma, and showed that deciding whether one has a winning strategy for Atropos is PSPACE-comple…
Friends-and-strangers is PSPACE-complete
Chao Yang, Zhujun Zhang
In this paper, we show that the friends-and-strangers problem is PSPACE-complete by reduction from the Ncl (non-deterministic constraint logic) problem.
Ricci-flat graphs with girth four
Weihua He, Jun Luo, Chao Yang +1
Lin-Lu-Yau introduced an interesting notion of Ricci curvature for graphs and obtained a complete characterization for all Ricci-flat graphs with girth at least five [1]. In this p…