Volltext-Downloads (blau) und Frontdoor-Views (grau)

Frequent Subgraph Mining in Outerplanar Graphs

  • In recent years there has been an increased interest in frequent pattern discovery in large databases of graph structured objects. While the frequent connected subgraph mining problem for tree datasets can be solved in incremental polynomial time, it becomes intractable for arbitrary graph databases. Existing approaches have therefore resorted to various heuristic strategies and restrictions of the search space, but have not identified a practically relevant tractable graph class beyond trees. In this paper, we define the class of so called tenuous outerplanar graphs, a strict generalization of trees, develop a frequent subgraph mining algorithm for tenuous outerplanar graphs that works in incremental polynomial time, and evaluate the algorithm empirically on the NCI molecular graph dataset.

Download full text files

Export metadata

Additional Services

Share in Twitter    Search Google Scholar    frontdoor_oas
Author:Tamas Horvath, Jan Ramon, Stefan Wrobel
Document Type:Conference Proceeding
Date of Publication (online):2011/04/21
Release Date:2011/04/21
Source:LWA 2006: Lernen - Wissensentdeckung - Adaptivität, Hildesheim, 9. - 11. Oktober 2006
PPN:Link zum Katalog
Contributor:Althoff, Klaus-Dieter
Institutes:Fachbereich IV / Informatik
DDC classes:000 Allgemeines, Informatik, Informationswissenschaft / 000 Allgemeines, Wissenschaft / 004 Informatik
Licence (German):License LogoDeutsches Urheberrecht