トポロジカルソートの定数時間列挙 Constant Time Generation of Linear Extensions

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

Given a poset P, several algorithms have been proposed for generating all linear extensions of P. The fastest known algorithm generates each linear extension in constant time "on average". In this paper we give a simple algorithm which generates each linear extension in constant time "in worst case". The known algorithm generates each linear extension exactly twice and output one of them, while our algorithm generates each linear extension exactly once.