Title: Frequent subgraph mining in outerplanar graphs
Authors: Horvath, Tamas ×
Ramon, Jan
Wrobel, Stefan #
Issue Date: Nov-2010
Publisher: Kluwer Academic Publishers
Series Title: Data Mining and Knowledge Discovery vol:21 issue:3 pages:472-508
Abstract: 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 consider the class of outerplanar graphs, a strict generalization of trees, develop a frequent subgraph mining algorithm for outerplanar graphs, and show that it works in incremental polynomial time for the practically relevant subclass of well-behaved outerplanar graphs, i.e., which have only polynomially many simple cycles.
We evaluate the algorithm empirically on chemo- and bioinformatics applications.
ISSN: 1384-5810
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
mrp4.pdfFull text Published 693KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science