1 citations · 1 across the 1 of their papers we have counts for
11 papers · 1 filter
Reconfiguration and Enumeration of Optimal Cyclic Ladder Lotteries
Yuta Nozaki, Kunihiro Wasa, Katsuhisa Yamanaka
A ladder lottery, known as ``Amidakuji'' in Japan, is a common way to decide an assignment at random. In this paper, we investigate reconfiguration and enumeration problems of cycl…
Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size
Alessio Conte, Roberto Grossi, Yasuaki Kobayashi +4
Graphlets of order in a graph are connected subgraphs induced by nodes (called -graphlets) or by edges (called edge -graphlets). They are among the interestin…
Independent set reconfiguration on directed graphs
Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi +4
\textsc{Directed Token Sliding} asks, given a directed graph and two sets of pairwise nonadjacent vertices, whether one can reach from one set to the other by repeatedly applying a…
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…
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…
The Perfect Matching Reconfiguration Problem
Marthe Bonamy, Nicolas Bousquet, Marc Heinrich +5
We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a fl…