Enumerating Algorithms of Graphs

点击翻译按钮获取中文摘要

In 2001, we have designed an efficient algorithm to enumerate all biconnected plane graphs. The algorithm enumerates such graphs in 0(1) time for each. The algorithm is presented in an international conference ICALP 2001.In this research we generalized the algorithm to many class of graphs, including triconnected maximal plane graphs with possibly some additional properties, trees with some degree properties, floorplans and some drawings, serias-parallel graphs, k-subsets, simplical polyhedrons, etc. Also we have implemented the algorithms and show the data at our web site. http://www.msc.cs.gunma-u.ac.jp/nakano_lab/Enu/enumeration.htmlMost of them output each object in 0(1) time for each. Furthermore it show a hidden tree structure among the objects.Especially, we have designed efficient enumeration algorithms for many kind of trees with some properties. Not only those algorithms solved many basic enumeration problems, But also such algorithms have an application for knowledge discovery. Many problem are modeled as a graph mining problem, which is a problem to find frequent subgraph in huge graphs (=XML data or WWW link networks). By using our enumeration algorithm such problem can be solved as follows. First we generate all objects with small size, then we check the occurrence of them. Then we find frequent subgraphs. Then we generate all objects with more larger objects only for the descendant objects of frequent subgraphs. By repeating the method, we can find all frequent subgraphs very efficiently.