Random Generation and Enumeration of Proper Interval Graphs

被引：0

作者：

Saitoh, Toshiki ^{[1
]}

Yamanaka, Katsuhisa ^{[2
]}

Kiyomi, Masashi ^{[1
]}

Uehara, Ryuhei ^{[1
]}

机构：

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

[2] Univ Electrocommun, Grad Sch Informat Syst, Chofu, Tokyo 1828585, Japan

来源：

WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS | 2009年 / 5431卷

关键词：

Counting; enumeration; proper interval graphs; random generation; unit interval graphs; BANDWIDTH MINIMIZATION PROBLEM; EFFICIENT GENERATION; COMPLETION PROBLEMS; RECOGNITION; ALGORITHM; REPRESENTATION; TREES;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We investigate connected proper interval graphs without vertex labels. We first give the number of connected proper interval graphs of n vertices. Using it, a simple algorithm that generates a connected proper interval graph uniformly at random up to isomorphism is presented. Finally an enumeration algorithm of connected proper interval graphs is proposed. The algorithm is based on the reverse search, and it outputs each connected proper interval graph in O(1) time.

引用

页码：177 / +

页数：4

共 36 条

[1]

[Anonymous], 1997, ENUMERATIVE COMBINAT

[2]

[Anonymous], 2005, ART COMPUTER PROGRAM

[3]

Arnold D. B., 1980, ACM Transactions on Programming Languages and Systems, V2, P122, DOI 10.1145/357084.357091

[4] Reverse search for enumeration [J].

Avis, D ;

Fukuda, K .

DISCRETE APPLIED MATHEMATICS, 1996, 65 (1-3) :21-46

[5] FINDING HAMILTONIAN CIRCUITS IN PROPER INTERVAL-GRAPHS [J].

BERTOSSI, AA .

INFORMATION PROCESSING LETTERS, 1983, 17 (02) :97-101

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

Bogart, KP ;

West, DB .

DISCRETE MATHEMATICS, 1999, 201 (1-3) :21-23

[7] A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths [J].

Bonichon, N .

DISCRETE MATHEMATICS, 2005, 298 (1-3) :104-114

[8]

Brandstadt A., 1999, Graph Classes: A Survey

[9] THE BANDWIDTH PROBLEM FOR GRAPHS AND MATRICES - A SURVEY [J].

CHINN, PZ ;

CHVATALOVA, J ;

DEWDNEY, AK ;

GIBBS, NE .

JOURNAL OF GRAPH THEORY, 1982, 6 (03) :223-254

[10]

DEFIGUEIREDO CMH, 1993, DCC0493 IC U EST CAM

← 1 2 3 4 →