著者

小野 顕光 中野 眞一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.105, no.72, pp.53-57, 2005-05-13

---

半順序集合Pが与えられたときに、すべてのトポロジカルソートを生成する幾つかのアルゴリズムが知られている.既知のアルゴリズムで最も高速なものは、各トポロジカルソートを"平均"定数時間で生成する.本文は, 各トポロジカルソートを定数時間で生成するアルゴリズムを与える.既知のアルゴリズムは, 各トポロジカルソートを丁度2回づつ生成し, そのうちの一方のみを出力するのに対し, 我々のアルゴリズムは各トポロジカルソートを丁度1回づつ生成する.