Title: Polynomial-delay enumeration of monotonic graph classes
Authors: Ramon, Jan ×
Nijssen, Siegfried #
Issue Date: Apr-2009
Publisher: MIT Press
Series Title: Journal of Machine Learning Research vol:10 pages:907-929
Abstract: Algorithms that list graphs such that no two listed graphs are isomorphic, are important building blocks of systems for mining and learning in graphs. Algorithms are already known that solve this problem efficiently for many classes of graphs of restricted topology, such as trees.
In this article we introduce the concept of a dense augmentation schema, and introduce an algorithm that can be used to enumerate any class of graphs with polynomial delay, as long as the class of graphs can be described using monotonic predicates and a dense augmentation schema. In practice this means that this is the first enumeration algorithm that can be applied theoretically efficiently in any frequent subgraph mining algorithm, and that this algorithm generalizes to situations beyond the standard frequent subgraph mining setting.
ISSN: 1532-4435
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
ramon09a.pdfMain article Published 200KbAdobe PDFView/Open


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

© Web of science