4 papers
Hardness of Forcing Unique Perfect Matchings in Bipartite Graphs of Maximum Degree 3
Ryoma Aoshima, Takashi Horiyama, Atsuki Nagao +4
In a graph , a set of edges is called a \emph{forcing set} if there exists a unique perfect matching such that . Similarly, a set of edges is called a…
On gapped repeats in a cyclic Fibonacci word
Takashi Horiyama, Yasuhide Numata, Kazuhisa Seto +1
In this article, we consider the words with cyclic indices. For given , we consider the pair of indices such that the word of length from is equal to the word…
On the complexity of finding a spanning even tree in a graph
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita +4
A tree is said to be even if for every pair of distinct leaves, the length of the unique path between them is even. In this paper we discuss the problem of determining whether an i…
Online and Offline Algorithms for Counting Distinct Closed Factors via Sliding Suffix Trees
Takuya Mieno, Shun Takahashi, Kazuhisa Seto +1
A string is said to be closed if its length is one, or if it has a non-empty factor that occurs both as a prefix and as a suffix of the string, but does not occur elsewhere. The no…