Title: Efficient frequent connected subgraph mining in graphs of bounded treewidth
Authors: Horvath, Tamas * ×
Ramon, Jan * #
Issue Date: 2010
Publisher: North-Holland Pub. Co.
Series Title: Theoretical Computer Science vol:411 pages:2784-2797
Abstract: The frequent connected subgraph mining problem, i.e., the problem
of listing all connected graphs that are subgraph isomorphic to at least
a certain number of transaction graphs of a database, cannot be solved
in output polynomial time in the general case. If, however, the transaction
graphs are restricted to forests then the problem becomes tractable.
In this paper we generalize the positive result on forests to graphs of
bounded treewidth. In particular, we show that for this class of transaction
graphs, frequent connected subgraphs can be listed in incremental
polynomial time. Since subgraph isomorphism remains NP-complete for
bounded treewidth graphs, the positive complexity result of this paper
shows that efficient frequent pattern mining is possible even for computationally
hard pattern matching operators.
ISSN: 0304-3975
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
* (joint) first author
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
tcs_1mar2010.pdfArticle draft Published 448KbAdobe PDFView/Open


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

© Web of science