グラフ的列の列挙

概要

論文の詳細を見る
単純グラフ G の各点の次数を降順に並べたものを G の次数列という。与えられた整数列 D がある単純グラフの次数列であるとき D はグラフ的列である。本文は、高々 n 個の整数からなるグラフ的列を、重複も抜けもれなく、列挙するアルゴリズムを提案する。Ruskey ら 3) は長さちょうど n のグラフ的列を列挙するアルゴリズムを提案し、それが Constant Amortized Time (CAT) アルゴリズムであることを実験的に示した。それに対して本論文では長さちょうど n のグラフ的列を列挙するアルゴリズムを提案し、それが CAT アルゴリズムである証明を与えた。本論文のアルゴリズムと Ruskey らのアルゴリズムは同様の方法で列挙を行っているが、本論文のアルゴリズムは 1 つのグラフ的列を最悪の場合でも定数時間で生成する。また、本論文では出力にかかる時間も考慮に入れて、計算時間について考察を行った。提案するアルゴリズムはすべてのグラフ的列を 1 つあたり O (1) 時間で列挙する。ただし、出力は直前のグラフ的列からの差分である。
2009-09-08