Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Efficient frequent connected induced subgraph mining in graphs of bounded treewidth
 Blockeel, H.: Machine learning and knowledge discovery in databases. Proceedings Pt. 1 : European conference, ECML PKDD 2013, Prague, Czech Republic, September 2327, 2013 Berlin: Springer, 2013 (Lecture Notes in Computer Science (LNCS) 8188) ISBN: 9783642409875 ISBN: 3642409873 ISBN: 9783642409882 S.622637 
 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) <2013, Prague> 

 Englisch 
 Konferenzbeitrag 
 Fraunhofer IAIS () 
Abstract
We study the frequent connected induced subgraph mining problem, i.e., the problem of listing all connected graphs that are induced subgraph isomorphic to a given number of transaction graphs. We first show that this problem cannot be solved for arbitrary transaction graphs in output polynomial time (if P NP) and then prove that for graphs of bounded treewidth, frequent connected induced subgraph mining is possible in incremental polynomial time by levelwise search. Our algorithm is an adaptation of the technique developed for frequent connected subgraph mining in bounded treewidth graphs. While the adaptation is relatively natural for many steps of the original algorithm, we need entirely different combinatorial arguments to show the correctness and efficiency of the new algorithm. Since induced subgraph isomorphism between bounded treewidth graphs is NPcomplete, the positive result of this paper provides another example of efficient pattern mining with respect to computationally intractable pattern matching operators.