5 citations · 25 across the 22 of their papers we have counts for
23 papers
The Upper Clique Transversal Problem: Hardness and Algorithms
Martin Milanič, Yushi Uno
A clique transversal in a graph is a set of vertices intersecting all maximal cliques. The problem of determining the minimum size of a clique transversal has received considerable…
Reconfiguration of Non-crossing Spanning Trees
Oswin Aichholzer, Brad Ballinger, Therese Biedl +7
For a set of points in the plane in general position, a non-crossing spanning tree is a spanning tree of the points where every edge is a straight-line segment between a pa…
Solving Rep-tile by Computers: Performance of Solvers and Analyses of Solutions
Mutsunori Banbara, Kenji Hashimoto, Takashi Horiyama +7
A rep-tile is a polygon that can be dissected into smaller copies (of the same size) of the original polygon. A polyomino is a polygon that is formed by joining one or more unit sq…
Yin-Yang Puzzles are NP-complete
Erik D. Demaine, Jayson Lynch, Mikhail Rudoy +1
We prove NP-completeness of Yin-Yang / Shiromaru-Kuromaru pencil-and-paper puzzles. Viewed as a graph partitioning problem, we prove NP-completeness of partitioning a rectangular g…
Gourds: a sliding-block puzzle with turning
Joep Hamersma, Marc van Kreveld, Yushi Uno +1
We propose a new kind of sliding-block puzzle, called Gourds, where the objective is to rearrange 1 x 2 pieces on a hexagonal grid board of 2n + 1 cells with n pieces, using slidin…
Linear-Time Recognition of Double-Threshold Graphs
Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi +1
A graph is a double-threshold graph if there exist a vertex-weight function and two real numbers s…
Reconfiguring Undirected Paths
Erik D. Demaine, David Eppstein, Adam Hesterberg +4
We consider problems in which a simple path of fixed length, in an undirected graph, is to be shifted from a start position to a goal position by moves that add an edge to either e…
Swapping Colored Tokens on Graphs
Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil +5
We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. Each pair of adjacent vertices ca…
Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces
Erik D. Demaine, Matias Korman, Jason S. Ku +6
We study the complexity of symmetric assembly puzzles: given a collection of simple polygons, can we translate, rotate, and possibly flip them so that their interior-disjoint union…
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…
Hanabi is NP-hard, Even for Cheaters who Look at Their Cards
Jean-Francois Baffier, Man-Kwun Chiu, Yago Diez +5
In this paper we study a cooperative card game called Hanabi from the viewpoint of algorithmic combinatorial game theory. In Hanabi, each card has one among colors and a number…
Threes!, Fives, 1024!, and 2048 are Hard
Stefan Langerman, Yushi Uno
We analyze the computational complexity of the popular computer games Threes!, 1024!, 2048 and many of their variants. For most known versions expanded to an m x n board, we show t…
Folding a Paper Strip to Minimize Thickness
Erik D. Demaine, David Eppstein, Adam Hesterberg +4
In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mo…
Parameterized Edge Hamiltonicity
Michael Lampis, Kazuhisa Makino, Valia Mitsou +1
We study the parameterized complexity of the classical Edge Hamiltonian Path problem and give several fixed-parameter tractability results. First, we settle an open question of Dem…
Morpion Solitaire 5D: a new upper bound of 121 on the maximum score
Akitoshi Kawamura, Takuma Okamoto, Yuichi Tatsu +2
Morpion Solitaire is a pencil-and-paper game for a single player. A move in this game consists of putting a cross at a lattice point and then drawing a line segment that passes thr…
Exact and fixed-parameter algorithms for metro-line crossing minimization problems
Yoshio Okamoto, Yuichi Tatsu, Yushi Uno
A metro-line crossing minimization problem is to draw multiple lines on an underlying graph that models stations and rail tracks so that the number of crossings of lines becomes mi…
(Total) Vector Domination for Graphs with Bounded Branchwidth
Toshimasa Ishii, Hirotaka Ono, Yushi Uno
Given a graph of order and an -dimensional non-negative vector , called demand vector, the vector domination (resp., total vector domina…
Mining Preserving Structures in a Graph Sequence
Takeaki Uno, Yushi Uno
In the recent research of data mining, frequent structures in a sequence of graphs have been studied intensively, and one of the main concern is changing structures along a sequenc…
On Complexity of Flooding Games on Graphs with Interval Representations
Hiroyuki Fukui, Yota Otachi, Ryuhei Uehara +2
The flooding games, which are called Flood-It, Mad Virus, or HoneyBee, are a kind of coloring games and they have been becoming popular online. In these games, each player colors o…
Solving Tantrix via Integer Programming
Fumika Kino, Yushi Uno
Tantrix is a puzzle to make a loop by connecting lines drawn on hexagonal tiles, and the objective of this research is to solve it by a computer. For this purpose, we give a proble…
The complexity of UNO
Erik D. Demaine, Martin L. Demaine, Nicholas J. A. Harvey +3
This paper investigates the popular card game UNO from the viewpoint of algorithmic combinatorial game theory. We define simple and concise mathematical models for the game, includ…
A tight upper bound on the (2,1)-total labeling number of outerplanar graphs
Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono +1
A -total labeling of a graph is an assignment from the vertex set and the edge set to the set of nonnegative integers such that $|f(x)-…
A linear time algorithm for L(2,1)-labeling of trees
Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono +1
An L(2,1)-labeling of a graph is an assignment from the vertex set to the set of nonnegative integers such that if and are adjacent and $|…