论文标题
有效的非同态图枚举算法，用于完美图的子类
Efficient Non-isomorphic Graph Enumeration Algorithms for Subclasses of Perfect Graphs
论文作者
论文摘要
相交图在图算法的区域进行了充分研究。已知某些相交图类具有通过反向搜索来列举所有未标记图的算法。由于这些算法一一输出图形，并且这些类中的图形数量很大，因此它们仅适用于少数顶点。二进制决策图（BDD）是各种数据的紧凑数据结构，可用于解决优化和枚举问题。这项研究提出了针对五个相交图类的枚举算法，该算法允许其成员图的$ \ mathrm {o}（n）$ - 位字符串表示形式。我们针对每个班级的算法列举了所有未标记的图表，而BDD上的$ N $顶点代表$ n $中的二进制字符串。此外，我们的算法被扩展为枚举在最大（BI）集团大小和/或边缘数量上的约束的算法。
Intersection graphs are well-studied in the area of graph algorithms. Some intersection graph classes are known to have algorithms enumerating all unlabeled graphs by reverse search. Since these algorithms output graphs one by one and the numbers of graphs in these classes are vast, they work only for a small number of vertices. Binary decision diagrams (BDDs) are compact data structures for various types of data and useful for solving optimization and enumeration problems. This study proposes enumeration algorithms for five intersection graph classes, which admit $\mathrm{O}(n)$-bit string representations for their member graphs. Our algorithm for each class enumerates all unlabeled graphs with $n$ vertices over BDDs representing the binary strings in time polynomial in $n$. Moreover, our algorithms are extended to enumerate those with constraints on the maximum (bi)clique size and/or the number of edges.
