21 citations · 62 across the 20 of their papers we have counts for
24 papers
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…
On the hardness of inclusion-wise minimal separators enumeration
Caroline Brosse, Oscar Defrain, Kazuhiro Kurita +3
Enumeration problems are often encountered as key subroutines in the exact computation of graph parameters such as chromatic number, treewidth, or treedepth. In the case of treedep…
Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids and Beyond
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
Finding a maximum cardinality common independent set in two matroids (also known as \textsc{Matroid Intersection}) is a classical combinatorial optimization problem, which generali…
Hardness of braided quantum circuit optimization in the surface code
Kunihiro Wasa, Shin Nishio, Koki Suetsugu +4
Large-scale quantum information processing requires the use of quantum error correcting codes to mitigate the effects of noise in quantum devices. Topological error-correcting code…
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…
An Approximation Algorithm for -best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints
Kazuhiro Kurita, Kunihiro Wasa
\emph{-best enumeration}, which asks to output -best solutions without duplication, is a helpful tool in data analysis for many fields. In such fields, graphs typically repre…
Reconfiguration of Regular Induced Subgraphs
Hiroshi Eto, Takehiro Ito, Yasuaki Kobayashi +2
We study the problem of checking the existence of a step-by-step transformation of -regular induced subgraphs in a graph, where and each step in the transformation mus…
Reconfiguring (non-spanning) arborescences
Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi +3
In this paper, we investigate the computational complexity of subgraph reconfiguration problems in directed graphs. More specifically, we focus on the problem of reconfiguring arbo…
Polynomial-Delay Enumeration of Large Maximal Matchings
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
Enumerating matchings is a classical problem in the field of enumeration algorithms. There are polynomial-delay enumeration algorithms for several settings, such as enumerating per…
Constant Amortized Time Enumeration of Eulerian trails
Kazuhiro Kurita, Kunihiro Wasa
In this paper, we consider enumeration problems for edge-distinct and vertex-distinct Eulerian trails. Here, two Eulerian trails are \emph{edge-distinct} if the edge sequences are…
Linear-Delay Enumeration for Minimal Steiner Problems
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
Kimelfeld and Sagiv [Kimelfeld and Sagiv, PODS 2006], [Kimelfeld and Sagiv, Inf. Syst. 2008] pointed out the problem of enumerating -fragments is of great importance in a keywor…
Efficient Constant-Factor Approximate Enumeration of Minimal Subsets for Monotone Properties with Weight Constraints
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
A property on a finite set is \emph{monotone} if for every satisfying , every superset of also satisfies . Many combinatorial prop…
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…
Constant Amortized Time Enumeration of Independent Sets for Graphs with Bounded Clique Number
Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura +1
In this study, we address the independent set enumeration problem. Although several efficient enumeration algorithms and careful analyses have been proposed for maximal independent…
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…
An Efficient Algorithm for Enumerating Chordal Bipartite Induced Subgraphs in Sparse Graphs
Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura +1
In this paper, we propose a characterization of chordal bipartite graphs and an efficient enumeration algorithm for chordal bipartite induced subgraphs. A chordal bipartite graph i…
Efficient Enumeration of Subgraphs and Induced Subgraphs with Bounded Girth
Kazuhiro Kurita, Kunihiro Wasa, Alessio Conte +2
The girth of a graph is the length of its shortest cycle. Due to its relevance in graph theory, network analysis and practical fields such as distributed computing, girth-related p…
Efficient Enumeration of Bipartite Subgraphs in Graphs
Kunihiro Wasa, Takeaki Uno
Subgraph enumeration problems ask to output all subgraphs of an input graph that belongs to the specified graph class or satisfy the given constraint. These problems have been wide…
Efficient Enumeration of Dominating Sets for Sparse Graphs
Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura +1
A dominating set of a graph is a set of vertices such that any vertex in is in or its neighbor is in . Enumeration of minimal dominating sets in a graph is one o…
Efficient Enumeration of Induced Matchings in a Graph without Cycles with Length Four
Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno +1
We address the induced matching enumeration problem. An edge set is an induced matching of a graph . The enumeration of matchings are widely studied in literature, bu…
Enumeration of Enumeration Algorithms
Kunihiro Wasa
In this paper, we enumerate enumeration problems and algorithms. This survey is under construction. If you know some results not in this survey or there is anything wrong, please l…
Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph
Kunihiro Wasa, Hiroki Arimura, Takeaki Uno
In this paper, we address the problem of enumerating all induced subtrees in an input k-degenerate graph, where an induced subtree is an acyclic and connected induced subgraph. A g…