For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Random Generation and Enumeration of Proper Interval Graphs
Toshiki SAITOH Katsuhisa YAMANAKA Masashi KIYOMI Ryuhei UEHARA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2010/07/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
counting, enumeration, proper interval graphs, random generation, unit interval graphs,
Full Text: PDF(282.6KB)>>
We investigate connected proper interval graphs without vertex labels. We first give the number of connected proper interval graphs of n vertices. Using this result, 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 reverse search, and it outputs each connected proper interval graph in (O)1 time.