2006 FrequentSubgraphMininginOuterpl

• (Horváth et al., 2006) ⇒ Tamás Horváth, Jan Ramon, and Stefan Wrobel. (2006). “Frequent Subgraph Mining in Outerplanar Graphs.” In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. doi:10.1145/1150402.1150427

Subject Headings: Graph Pattern Mining.

Cited By

• http://scholar.google.com/scholar?q=%22Frequent+subgraph+mining+in+outerplanar+graphs%22+2006
• http://dl.acm.org/citation.cfm?id=1150402.1150427&preflayout=flat#citedby

Quotes

Author Keywords

• computational chemistry; frequent pattern discovery; graph mining

Abstract

In recent years there has been an increased interest in algorithms that can perform 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.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2006 FrequentSubgraphMininginOuterpl	Jan Ramon Tamás Horváth Stefan Wrobel			Frequent Subgraph Mining in Outerplanar Graphs				10.1145/1150402.1150427