15 citations · 65 across the 24 of their papers we have counts for
18 papers · 1 filter
A Compact DAG for Storing and Searching Maximal Common Subsequences
Alessio Conte, Roberto Grossi, Giulia Punzi +1
Maximal Common Subsequences (MCSs) between two strings X and Y are subsequences of both X and Y that are maximal under inclusion. MCSs relax and generalize the well known and widel…
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…
Proximity Search For Maximal Subgraph Enumeration
Alessio Conte, Andrea Marino, Roberto Grossi +2
This paper proposes a new general technique for maximal subgraph enumeration which we call proximity search, whose aim is to design efficient enumeration algorithms for problems th…
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…