Random Generation and Enumeration of Bipartite Permutation Graphs
Random Generation and Enumeration of Bipartite Permutation Graphs
复制标题
二分排列图的随机生成和枚举
DOI：
10.1016/j.jda.2011.11.001
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
and R. Uehara
中科院分区：
文献类型：
--
作者：
T. Saitoh;Y. Otachi;K. Yamanaka;and R. Uehara
研究了不带顶点标号的连通二部置换图。首先给出n阶连通二部置换图的个数。在此基础上，给出了一个随机一致生成连通二部置换图直至同构的简单算法。最后给出了连通二部置换图的计数算法。该算法基于反向搜索，在O（1）时间内输出每个连通二部置换图。
Connected bipartite permutation graphs without vertex labels are investigated. First, the number of connected bipartite permutation graphs of n vertices is given. Based on the number, a simple algorithm that generates a connected bipartite permutation graph uniformly at random up to isomorphism is presented. Finally an enumeration algorithm of connected bipartite permutation graphs is proposed. The algorithm is based on reverse search, and it outputs each connected bipartite permutation graph in O(1) time.