Random Generation and Enumeration of Proper Interval Graphs

Toshiki SAITOH  Katsuhisa YAMANAKA  Masashi KIYOMI  Ryuhei UEHARA  

IEICE TRANSACTIONS on Information and Systems   Vol.E93-D   No.7   pp.1816-1823
Publication Date: 2010/07/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.1816
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)>>
Buy this Article

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.