Title: Efficient frequent connected subgraph mining in graphs of bounded treewidth
Authors: Horvath, Tamas ×
Ramon, Jan #
Issue Date: Sep-2008
Publisher: Springer
Series Title: Lecture notes in computer science vol:5211 pages:520-535
Conference: Principles and Practice of Knowledge Discovery in Databases location:Antwerp, Belgium date:15 - 19 September 2008
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 specified number of elements of a database of transaction graphs, cannot be solved in output polynomial time in the general case. If, however, the transaction graphs are restricted to trees then the problem becomes tractable. In this paper, we generalize the positive complexity result on trees to graphs of bounded treewidth. In particular, we show that for this class of transaction graphs, frequent connected subgraphs can be listed with incremental polynomial delay. Since subgraph isomorphism remains NP-complete for bounded treewidth graphs, the positive complexity result of this paper implies that efficient frequent pattern mining is possible even for computationally hard pattern matching operators.
Description: Acceptance rate = 104/521 = 20%
ISBN: 978-3-540-87478-2
ISSN: 0302-9743
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
pkdd08.pdfmain article Published 226KbAdobe PDFView/Open


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

© Web of science