偏序的线性扩展的传递约简

Question

是否存在一种有效的算法来从一个偏序的线性扩展中创建传递约简?

Update:实际上，偏序是已知的。我也意识到计算给定偏阶的传递约简的时间复杂度。我想知道的是:给定一个偏阶和它的一个线性扩展，时间复杂度可以降低吗?

Answer 1

渐进地说，答案是否定的。(n + m)的下界很简单，因为必须检查整个输入，并且拓扑排序在时间O(n + m)内产生线性扩展，这不会给任何正确的算法增加渐近代价。

Answer 2

如果我对问题的理解正确的话，可以通过使用与输入编码长度线性的拓扑排序来生成偏序的线性扩展。按照您问题中的链接，生成的序列已经是自身的传递约简，因为它的传递闭包是相同的可达性关系。但是，请注意，初始偏序的线性扩展可能不是唯一确定的。