The search functionality is under construction.
The search functionality is under construction.

Random Generation and Enumeration of Proper Interval Graphs

Toshiki SAITOH, Katsuhisa YAMANAKA, Masashi KIYOMI, Ryuhei UEHARA

  • Full Text Views

    0

  • Cite this

Summary :

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.

Publication
IEICE TRANSACTIONS on Information Vol.E93-D No.7 pp.1816-1823
Publication Date
2010/07/01
Publicized
Online ISSN
1745-1361
DOI
10.1587/transinf.E93.D.1816
Type of Manuscript
PAPER
Category
Fundamentals of Information Systems

Authors

Keyword