4 citations · 9 across the 9 of their papers we have counts for
8 papers · 1 filter
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…
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…
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…