Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs

被引：10

作者：

Yamazaki, Kazuaki ^{[1
]}

Saitoh, Toshiki ^{[2
]}

Kiyomi, Masashi ^{[3
]}

Uehara, Ryuhei ^{[1
]}

机构：

[1] JAIST, Sch Informat Sci, Nomi, Japan

[2] Kyushu Inst Technol, Sch Comp Sci & Syst Engn, Kitakyushu, Fukuoka, Japan

[3] Yokohama City Univ, Sch Data Sci, Yokohama, Kanagawa, Japan

来源：

THEORETICAL COMPUTER SCIENCE | 2020年 / 806卷 / 806期

关键词：

Enumeration; Graph isomorphism; Interval graph; Permutation graph; Reverse search; Nonisomorphic graphs; LINEAR-TIME ALGORITHM; RANDOM GENERATION; TREES;

D O I：

10.1016/j.tcs.2019.04.017

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, a general framework for enumerating every element in a graph class is given. The main feature of this framework is that it is designed to enumerate only nonisomorphic graphs in a graph class. Applying this framework to the classes of interval graphs and permutation graphs, we give efficient enumeration algorithms for these graph classes such that each element in the class is output in a polynomial time delay. The experimental results are also given. The catalogs of graphs in these graph classes are also provided. (C) 2019 Published by Elsevier B.V.

引用

页码：310 / 322

页数：13

共 20 条

[1] Reverse search for enumeration [J].