Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

On the complexity of frequent subtree mining in very simple structures

: Welke, P.; Horvath, T.; Wrobel, S.


Davis, J.:
Inductive logic programming. 24th international conference, ILP 2014 : Nancy, France, September 14-16, 2014: Revised selected papers
Cham: Springer International Publishing, 2015 (Lecture Notes in Computer Science 9046)
ISBN: 978-3-319-23707-7 (Print)
ISBN: 978-3-319-23708-4 (Online)
International Conference on Inductive Logic Programming (ILP) <24, 2014, Nancy>
Fraunhofer IAIS ()

We study the complexity of frequent subtree mining in very simple graphs beyond forests. We show for d-tenuous outerplanar graphs that frequent subtrees can be listed with polynomial delay if the cycle degree, i.e., the maximum number of blocks that share a common vertex, is bounded by some constant. The crucial step in the proof of this positive result is a polynomial time algorithm deciding subgraph isomorphism from trees into d-tenuous outerplanar graphs of bounded cycle degree. We obtain this algorithm by generalizing the algorithm of Shamir and Tsur that decides subgraph isomorphism between trees. Our results may also be of some interest to algorithmic graph theory, as they indicate that even for very simple structures, the cycle degree is a crucial parameter for the tractability of subgraph isomorphism. We also discuss some interesting problems towards generalizing the positive result of this work.