- Integration of CiNii Books functions for fiscal year 2025 has completed
- Trial version of CiNii Research Knowledge Graph Search feature is available on CiNii Labs
- 【Updated on November 26, 2025】Regarding the recording of “Research Data” and “Evidence Data”
- Start the collection of all publicly IRDB content
- Incorporate Research Data from KAKEN
Random Generation and Enumeration of Proper Interval Graphs
-
- KIYOMI Masashi
- Japan Advanced Institute of Science and Technology
-
- UEHARA Ryuhei
- Japan Advanced Institute of Science and Technology
-
- SAITOH Toshiki
- Japan Advanced Institute of Science and Technology
-
- YAMANAKA Katsuhisa
- University of Electro-Communications
Bibliographic Information
- Published
- 2010
- Resource Type
- journal article
- DOI
-
- 10.1587/transinf.e93.d.1816
- 10.1007/978-3-642-00202-1_16
- Publisher
- The Institute of Electronics, Information and Communication Engineers
Search this article
Description
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.
Journal
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E93.D (7), 1816-1823, 2010
The Institute of Electronics, Information and Communication Engineers
- Tweet
Details 詳細情報について
-
- CRID
- 1390001204378187648
-
- NII Article ID
- 10027363849
-
- NII Book ID
- AA10826272
-
- ISSN
- 17451361
- 16113349
- 09168532
- 03029743
-
- HANDLE
- 10228/00006356
-
- Text Lang
- en
-
- Article Type
- journal article
-
- Data Source
-
- JaLC
- IRDB
- Crossref
- CiNii Articles
- KAKEN
- OpenAIRE
-
- Abstract License Flag
- Disallowed
