7 papers
The Complexity of Maximal/Closed Frequent Tree Mining for Bounded Height Trees
Kenta Komoto, Kazuhiro Kurita, Hirotaka Ono
Frequent tree mining asks us to enumerate tree patterns that occur frequently in a database of rooted trees. This problem is motivated by tree-structured data in bioinformatics, su…
Further Results on Rendering Geometric Intersection Graphs Sparse by Dispersion
Nicolás Honorato-Droguett, Kazuhiro Kurita, Tesshu Hanaka +2
Removing overlaps is a central task in domains such as scheduling, visibility, and map labelling. This can be modelled using graphs, where overlap removals correspond to enforcing…
On the Complexity of Minimising the Moving Distance for Dispersing Objects
Nicolás Honorato-Droguett, Kazuhiro Kurita, Tesshu Hanaka +1
We study Geometric Graph Edit Distance (GGED), a graph-editing model to compute the minimum edit distance of intersection graphs that uses moving objects as an edit operation. We f…
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…
Algorithms for Optimally Shifting Intervals under Intersection Graph Models
Nicolás Honorato-Droguett, Kazuhiro Kurita, Tesshu Hanaka +1
In well-studied graph modification problems, adding and deleting vertices and edges are used as graph editing operations. We propose a model for graph modification on geometric int…