Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430596 | Journal of Discrete Algorithms | 2012 | 14 Pages |
Abstract
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)O(1) time.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Toshiki Saitoh, Yota Otachi, Katsuhisa Yamanaka, Ryuhei Uehara,