Random Generation and Enumeration of Bipartite Permutation Graphs

• Saitoh, Toshiki

• Otachi, Yota

• Yamanaka, Katsuhisa

• Uehara, Ryuhei

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) time.

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/10720

Journal

• Journal of Discrete Algorithms

  Journal of Discrete Algorithms 10 84-97, 2011-11-18

  Elsevier

Keywords

• Bipartite permutation graph
• counting
• Dyck path
• enumeration
• Motzkin path
• random generation

Details

• CRID: 1050282812515064576
• NII Article ID: 120004680901
• ISSN: 15708667
• Web Site: http://hdl.handle.net/10119/10720
• Text Lang: en
• Article Type: journal article
• Data Source:
  • IRDB
  • CiNii Articles