- 著者
-
小野 顕光
中野 眞一
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)
- 巻号頁・発行日
- vol.105, no.72, pp.53-57, 2005-05-13
半順序集合Pが与えられたときに、すべてのトポロジカルソートを生成する幾つかのアルゴリズムが知られている.既知のアルゴリズムで最も高速なものは、各トポロジカルソートを"平均"定数時間で生成する.本文は, 各トポロジカルソートを定数時間で生成するアルゴリズムを与える.既知のアルゴリズムは, 各トポロジカルソートを丁度2回づつ生成し, そのうちの一方のみを出力するのに対し, 我々のアルゴリズムは各トポロジカルソートを丁度1回づつ生成する.