6 citations · 17 across the 20 of their papers we have counts for
22 papers
Finding One Local Optimum Is Easy -- but What About Two?
Yasuaki Kobayashi, Kazuhiro Kurita, Yutaro Yamaguchi
The class PLS (Polynomial Local Search) captures the complexity of finding a solution that is locally optimal and has proven to be an important concept in the theory of local searc…
The Complexity of Maximal Common Subsequence Enumeration
Giovanni Buzzega, Alessio Conte, Yasuaki Kobayashi +2
Frequent pattern mining is widely used to find ``important'' or ``interesting'' patterns in data. While it is not easy to mathematically define such patterns, maximal frequent patt…
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…
Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
Yasuaki Kobayashi, Kazuhiro Kurita, Kevin Mann +2
In this paper, we consider the problems of enumerating minimal vertex covers and minimal dominating sets with capacity and/or connectivity constraints. We develop polynomial-delay…
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…
Optimal LZ-End Parsing is Hard
Hideo Bannai, Mitsuru Funakoshi, Kazuhiro Kurita +3
LZ-End is a variant of the well-known Lempel-Ziv parsing family such that each phrase of the parsing has a previous occurrence, with the additional constraint that the previous occ…
Frameworks to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems
Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi +4
Finding a \emph{single} best solution is the most common objective in combinatorial optimization problems. However, such a single solution may not be applicable to real-world probl…
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…
Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita +2
Finding diverse solutions in combinatorial problems recently has received considerable attention (Baste et al. 2020; Fomin et al. 2020; Hanaka et al. 2021). In this paper we study…
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…
An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion
Yuuki Aoike, Tatsuya Gima, Tesshu Hanaka +5
A cactus is a connected graph that does not contain as a minor. Given a graph and integer , Cactus Vertex Deletion (also known as Diamond Hitting Se…
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…
Finding Diverse Trees, Paths, and More
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita +1
Mathematical modeling is a standard approach to solve many real-world problems and {\em diversity} of solutions is an important issue, emerging in applying solutions obtained from…
Efficient Enumerations for Minimal Multicuts and Multiway Cuts
Kazuhiro Kurita, Yasuaki Kobayashi
Let be an undirected graph and let be a set of terminal pairs. A node/edge multicut is a subset of vertices/edges of whose removal destroy…
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…
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 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…