4 citations · 9 across the 9 of their papers we have counts for
16 papers
Reconfiguration of Time-Respecting Arborescences
Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama +4
An arborescence, which is a directed analogue of a spanning tree in an undirected graph, is one of the most fundamental combinatorial objects in a digraph. In this paper, we study…
ZDD-Based Algorithmic Framework for Solving Shortest Reconfiguration Problems
Takehiro Ito, Jun Kawahara, Yu Nakahata +4
This paper proposes an algorithmic framework for various reconfiguration problems using zero-suppressed binary decision diagrams (ZDDs), a data structure for families of sets. In g…
Sorting Balls and Water: Equivalence and Computational Complexity
Takehiro Ito, Jun Kawahara, Shin-ichi Minato +7
Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled…
Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint
Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi +4
We investigate the complexity of finding a transformation from a given spanning tree in a graph to another given spanning tree in the same graph via a sequence of edge flips. The e…
Fixed-Parameter Algorithms for Graph Constraint Logic
Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito +3
Non-deterministic constraint logic (NCL) is a simple model of computation based on orientations of a constraint graph with edge weights and vertex demands. NCL captures \PSPACE\xsp…
Reconfiguration of Spanning Trees with Many or Few Leaves
Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi +4
Let be a graph and be two spanning trees of . We say that can be transformed into via an edge flip if there exist two edges and in $T_2…
Trichotomy for the reconfiguration problem of integer linear systems
Kei Kimura, Akira Suzuki
In this paper, we consider the reconfiguration problem of integer linear systems. In this problem, we are given an integer linear system and two feasible solutions $\boldsymbol…
Reconfiguring k-path vertex covers
Duc A. Hoang, Akira Suzuki, Tsuyoshi Yagita
A vertex subset of a graph is called a -path vertex cover if every path on vertices in contains at least one vertex from . The \textsc{-Path Vertex Cover R…
Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
Alexandre Blanché, Haruka Mizuta, Paul Ouvrard +1
Given a dominating set, how much smaller a dominating set can we find through elementary operations? Here, we proceed by iterative vertex addition and removal while maintaining the…
Incremental Optimization of Independent Sets under Reachability Constraints
Takehiro Ito, Haruka Mizuta, Naomi Nishimura +1
We introduce a new framework for reconfiguration problems, and apply it to independent sets as the first example. Suppose that we are given an independent set of a graph ,…
Reconfiguring spanning and induced subgraphs
Tesshu Hanaka, Takehiro Ito, Haruka Mizuta +5
Subgraph reconfiguration is a family of problems focusing on the reachability of the solution space in which feasible solutions are subgraphs, represented either as sets of vertice…
The Complexity of (List) Edge-Coloring Reconfiguration Problem
Hiroki Osawa, Akira Suzuki, Takehiro Ito +1
Let be a graph such that each edge has its list of available colors, and assume that each list is a subset of the common set consisting of colors. Suppose that we are given…
The complexity of dominating set reconfiguration
Arash Haddadan, Takehiro Ito, Amer E. Mouawad +4
Suppose that we are given two dominating sets and of a graph whose cardinalities are at most a given threshold . Then, we are asked whether there exists a sequen…
Computational Complexity of Competitive Diffusion on (Un)weighted Graphs
Takehiro Ito, Yota Otachi, Toshiki Saitoh +6
Consider an undirected graph modeling a social network, where the vertices represent users, and the edges do connections among them. In the competitive diffusion game, each of a nu…
Reconfiguration of Dominating Sets
Akira Suzuki, Amer E. Mouawad, Naomi Nishimura
We explore a reconfiguration version of the dominating set problem, where a dominating set in a graph is a set of vertices such that each vertex is either in or has a n…
On the Parameterized Complexity of Reconfiguration Problems
Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman +2
We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration version of an optimization problem takes as input two feasible…