5 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…
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…
Computing diverse pair of solutions for tractable SAT
Tatsuya Gima, Yuni Iwamasa, Yasuaki Kobayashi +3
In many decision-making processes, one may prefer multiple solutions to a single solution, which allows us to choose an appropriate solution from the set of promising solutions tha…
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 p…