3 papers
cs.CC2023
On the Computational Complexity of Generalized Common Shape Puzzles
Mutsunori Banbara, Shin-ichi Minato, Hirotaka Ono +1
In this study, we investigate the computational complexity of some variants of generalized puzzles. We are provided with two sets S_1 and S_2 of polyominoes. The first puzzle asks…
cs.DS2023
Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP
Tesshu Hanaka, Hirotaka Ono, Kosuke Sugiyama
In this paper, we give a simple polynomial-time reduction of {L(p)-Labeling} on graphs with a small diameter to {Metric (Path) TSP}, which enables us to use numerous results on {(M…
cs.DS2023
Grouped Domination Parameterized by Vertex Cover, Twin Cover, and Beyond
Tesshu Hanaka, Hirotaka Ono, Yota Otachi +1
A dominating set of graph is called an -grouped dominating set if can be partitioned into such that the size of each unit is and the s…