Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. On the complexity of frequent subtree mining in very simple structures
 Davis, J.: Inductive logic programming. 24th international conference, ILP 2014 : Nancy, France, September 1416, 2014: Revised selected papers Cham: Springer International Publishing, 2015 (Lecture Notes in Computer Science 9046) ISBN: 9783319237077 (Print) ISBN: 9783319237084 (Online) S.194209 
 International Conference on Inductive Logic Programming (ILP) <24, 2014, Nancy> 

 Englisch 
 Konferenzbeitrag 
 Fraunhofer IAIS () 
Abstract
We study the complexity of frequent subtree mining in very simple graphs beyond forests. We show for dtenuous 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 dtenuous 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.