IEICE TRANSACTIONS on Information
Random Generation and Enumeration of Proper Interval Graphs
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
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Toshiki SAITOH, Katsuhisa YAMANAKA, Masashi KIYOMI, Ryuhei UEHARA, "Random Generation and Enumeration of Proper Interval Graphs" in IEICE TRANSACTIONS on Information,
vol. E93-D, no. 7, pp. 1816-1823, July 2010, doi: 10.1587/transinf.E93.D.1816.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E93.D.1816/_p
Copy
@ARTICLE{e93-d_7_1816,
author={Toshiki SAITOH, Katsuhisa YAMANAKA, Masashi KIYOMI, Ryuhei UEHARA, },
journal={IEICE TRANSACTIONS on Information},
title={Random Generation and Enumeration of Proper Interval Graphs},
year={2010},
volume={E93-D},
number={7},
pages={1816-1823},
abstract={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.},
keywords={},
doi={10.1587/transinf.E93.D.1816},
ISSN={1745-1361},
month={July},}
Copy
TY - JOUR
TI - Random Generation and Enumeration of Proper Interval Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 1816
EP - 1823
AU - Toshiki SAITOH
AU - Katsuhisa YAMANAKA
AU - Masashi KIYOMI
AU - Ryuhei UEHARA
PY - 2010
DO - 10.1587/transinf.E93.D.1816
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E93-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2010
AB - 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.
ER -
English
