Random Generation and Enumeration of Bipartite Permutation Graphs

被引：0

作者：

Saitoh, Toshiki ^{[1
]}

Otachi, Yota ^{[2
]}

Yamanaka, Katsuhisa ^{[3
]}

Uehara, Ryuhei ^{[4
]}

机构：

[1] JST, MINATO Discrete Struct Manipulat Syst Project, ERATO, North 14,West 9, Sapporo, Hokkaido 0600814, Japan

[2] Tohoku Univ, Grad Sch Informat Sci, Sendai, Miyagi 9808579, Japan

[3] Iwate Univ, Dept Elect Engn & Comp Sci, Iwama, Iwate 0208550, Japan

[4] JAIST, Sch Informat Sci, Asahidai 1-1, Nomi, Ishikawa 9231292, Japan

来源：

ALGORITHMS AND COMPUTATION, PROCEEDINGS | 2009年 / 5878卷

关键词：

Bipartite permutation graph; counting; Dyck path; enumeration; Motzkin path; random generation; PROPER; REPRESENTATION;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 the reverse search, and it outputs each connected bipartite permutation graph in O(1) time.

引用

页码：1104 / +

页数：2

共 20 条

[1]

[Anonymous], 2005, ART COMPUTER PROGRAM

[2]

[Anonymous], 1997, Enumerative combinatorics

[3] A short proof that 'proper = unit' [J].