Enumerating Algorithms of Graphs

在2001年，我们设计了一个有效的算法来枚举所有的双连通平面图。该算法在0(1)时间内为每个图枚举这样的图。该算法在ICALP 2001国际会议上提出。在本研究中，我们将该算法推广到许多类型的图，包括可能带有一些附加性质的三连通极大平面图，带有一些度性质的树，平面图和一些图纸，串行并行图，k子集，简单多面体等。我们还实现了算法，并在我们的网站上显示了数据。http://www.msc.cs.gunma-u.ac.jp/nakano_lab/Enu/enumeration.htmlMost它们在0(1)个时间内输出每个对象。此外，它还显示了对象之间的隐藏树结构。特别地，我们针对多种具有一定性质的树设计了高效的枚举算法。这些算法不仅解决了许多基本的枚举问题，而且在知识发现方面也有应用。许多问题被建模为图挖掘问题，即在庞大的图（=XML数据或WWW链接网络）中发现频繁子图的问题。使用我们的枚举算法可以求解如下问题。首先我们生成所有小尺寸的对象，然后检查它们的出现情况。然后我们找到频繁子图。然后我们用更大的对象生成所有对象，只针对频繁子图的后代对象。通过重复该方法，我们可以非常有效地找到所有的频繁子图。

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.