BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Yushi Uno

Yushi Uno appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsDiscrete MathematicsComputational ComplexityComputational GeometryComputer Science and Game Theorymath.CO

Catalog footprint

What is connected

13works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

13 published item(s)

preprint2022arXiv

Reconfiguration of Non-crossing Spanning Trees

For a set $P$ of $n$ 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 pair of points and no two edges intersect except at a common endpoint. We study the problem of reconfiguring one non-crossing spanning tree of $P$ to another using a sequence of flips where each flip removes one edge and adds one new edge so that the result is again a non-crossing spanning tree of $P$. There is a known upper bound of $2n-4$ flips [Avis and Fukuda, 1996] and a lower bound of $1.5n - 5$ flips. We give a reconfiguration algorithm that uses at most $2n-3$ flips but reduces that to $1.5n-2$ flips when one tree is a path and either: the points are in convex position; or the path is monotone in some direction. For points in convex position, we prove an upper bound of $2d - Ω(\log d)$ where $d$ is half the size of the symmetric difference between the trees. We also examine whether the happy edges (those common to the initial and final trees) need to flip, and we find exact minimum flip distances for small point sets using exhaustive search.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Single-Player and Two-Player Buttons & Scissors Games

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-complete for $C = 2$ colors but polytime solvable for $C = 1$. Similarly the game is NP-complete if every color is used by at most $F = 4$ buttons but polytime solvable for $F \leq 3$. We also consider restrictions on the board size, cut directions, and cut sizes. Finally, we introduce several natural two-player versions of the game and show that they are PSPACE-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Folding a Paper Strip to Minimize Thickness

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 mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to two metrics: minimizing the total number of layers in the folded state (so that a "flat folding" is indeed close to flat), and minimizing the total amount of paper required to execute the folding (where "thicker" creases consume more paper). We prove both problems strongly NP-complete even for 1D folding. On the other hand, we prove the first problem fixed-parameter tractable in 1D with respect to the number of layers.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Morpion Solitaire 5D: a new upper bound of 121 on the maximum score

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 through exactly five consecutive crosses. The objective is to make as many moves as possible, starting from a standard initial configuration of crosses. For one of the variants of this game, called 5D, we prove an upper bound of 121 on the number of moves. This is done by introducing line-based analysis, and improves the known upper bound of 138 obtained by potential-based analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Parameterized Edge Hamiltonicity

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 Demaine et al. by showing that Edge Hamiltonian Path is FPT parameterized by vertex cover, and that it also admits a cubic kernel. We then show fixed-parameter tractability even for a generalization of the problem to arbitrary hypergraphs, parameterized by the size of a (supplied) hitting set. We also consider the problem parameterized by treewidth or clique-width. Surprisingly, we show that the problem is FPT for both of these standard parameters, in contrast to its vertex version, which is W-hard for clique-width. Our technique, which may be of independent interest, relies on a structural characterization of clique-width in terms of treewidth and complete bipartite subgraphs due to Gurski and Wanke.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

(Total) Vector Domination for Graphs with Bounded Branchwidth

Given a graph $G=(V,E)$ of order $n$ and an $n$-dimensional non-negative vector $d=(d(1),d(2),\ldots,d(n))$, called demand vector, the vector domination (resp., total vector domination) is the problem of finding a minimum $S\subseteq V$ such that every vertex $v$ in $V\setminus S$ (resp., in $V$) has at least $d(v)$ neighbors in $S$. The (total) vector domination is a generalization of many dominating set type problems, e.g., the dominating set problem, the $k$-tuple dominating set problem (this $k$ is different from the solution size), and so on, and its approximability and inapproximability have been studied under this general framework. In this paper, we show that a (total) vector domination of graphs with bounded branchwidth can be solved in polynomial time. This implies that the problem is polynomially solvable also for graphs with bounded treewidth. Consequently, the (total) vector domination problem for a planar graph is subexponential fixed-parameter tractable with respectto $k$, where $k$ is the size of solution.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Exact and fixed-parameter algorithms for metro-line crossing minimization problems

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 minimum. It has several variations by adding restrictions on how lines are drawn. Among those, there is one with a restriction that line terminals have to be drawn at a verge of a station, and it is known to be NP-hard even when underlying graphs are paths. This paper studies the problem in this setting, and propose new exact algorithms. We first show that a problem to decide if lines can be drawn without crossings is solved in polynomial time, and propose a fast exponential algorithm to solve a crossing minimization problem. We then propose a fixed-parameter algorithm with respect to the multiplicity of lines, which implies that the problem is FPT.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On Complexity of Flooding Games on Graphs with Interval Representations

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 one specified cell in his/her turn, and all connected neighbor cells of the same color are also colored by the color. This flooding or coloring spreads on the same color cells. It is natural to consider these new coloring games on more general boards, or general graphs. Recently, computational complexities of the variants of the flooding games on several graph classes have been studied. In this paper, we investigate the flooding games on some graph classes characterized by interval representations. Our results state that the number of colors is a key parameter to determine the computational complexity of the flooding games. When the number of colors is a fixed constant, these games can be solved in polynomial time on an interval graph. On the other hand, if the number of colors is not bounded, the flooding game is NP-complete on a proper interval graph. We also state similar results for split graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The complexity of UNO

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, including both cooperative and uncooperative versions, and analyze their computational complexity. In particular, we prove that even a single-player version of UNO is NP-complete, although some restricted cases are in P. Surprisingly, we show that the uncooperative two-player version is also in P.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Mining Preserving Structures in a Graph Sequence

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 sequence of graphs that can capture dynamic properties of data. On the contrary, we newly focus on "preserving structures" in a graph sequence that satisfy a given property for a certain period, and mining such structures is studied. As for an onset, we bring up two structures, a connected vertex subset and a clique that exist for a certain period. We consider the problem of enumerating these structures. and present polynomial delay algorithms for the problems. Their running time may depend on the size of the representation, however, if each edge has at most one time interval in the representation, the running time is O(|V||E|^3) for connected vertex subsets and O(min{Δ^5, |E|^2Δ}) for cliques, where the input graph is G = (V,E) with maximum degree Δ. To the best of our knowledge, this is the first approach to the treatment of this notion, namely, preserving structures.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Solving Tantrix via Integer Programming

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 problem setting of solving Tantrix as arranging tiles in an appropriate shape and making a loop at the same time within a given hexagonal lattice board. We then formulate it as an integer program by expressing the rules of Tantrix as its constraints, and solve it by a mathematical programming solver to have a solution. As a result, we establish a formulation that solves Tantrix of moderate sizes, and even when the solutions are invalid only by elementary constraints, we achieved it by introducing additional constraints and an artificial objective function to avoid flaws in invalid solutions. By this approach we are successful in solving Tantrix of size up to 50.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A linear time algorithm for L(2,1)-labeling of trees

An L(2,1)-labeling of a graph $G$ is an assignment $f$ from the vertex set $V(G)$ to the set of nonnegative integers such that $|f(x)-f(y)|\ge 2$ if $x$ and $y$ are adjacent and $|f(x)-f(y)|\ge 1$ if $x$ and $y$ are at distance 2, for all $x$ and $y$ in $V(G)$. A $k$-L(2,1)-labeling is an assignment $f:V(G)\to\{0,..., k\}$, and the L(2,1)-labeling problem asks the minimum $k$, which we denote by $λ(G)$, among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of a very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been $\mO(Δ^{4.5} n)$ for more than a decade, however, an $\mO(n^{1.75})$-time algorithm has been proposed recently, which substantially improved the previous one, where $Δ$ is the maximum degree of $T$ and $n=|V(T)|$. In this paper, we finally establish a linear time algorithm for L(2,1)-labeling of trees.

0 citations0 reviewsNo code linkedOpen access