偏序线性扩展的传递归约
Transitive reduction from a linear extension of a partial order
是否有创建偏序 transitive reduction from a single linear extension 的有效算法？
更新： 其实偏序是已知的。我也知道给定偏序的 time complexity of computing a transitive reduction。我想知道的是：给定一个偏序和它的线性扩展之一，时间复杂度可以降低吗？
如果我对问题的理解正确，可以通过使用输入编码长度的 topological sorting 时间线性来生成偏序的线性扩展。在您问题中的 link 之后，生成的序列已经是自身的传递归约，因为它的传递闭包是相同的可达性关系。但是，请注意初始偏序的线性扩展可能不是唯一确定的。
渐近地讲，答案是否定的。只需检查整个输入，Omega(n + m) 就有一个微不足道的下界，拓扑排序会在时间上产生线性扩展 O(n + m)，这不会给任何正确的算法增加渐近成本。
是否有创建偏序 transitive reduction from a single linear extension 的有效算法？
更新： 其实偏序是已知的。我也知道给定偏序的 time complexity of computing a transitive reduction。我想知道的是：给定一个偏序和它的线性扩展之一，时间复杂度可以降低吗？
如果我对问题的理解正确，可以通过使用输入编码长度的 topological sorting 时间线性来生成偏序的线性扩展。在您问题中的 link 之后，生成的序列已经是自身的传递归约，因为它的传递闭包是相同的可达性关系。但是，请注意初始偏序的线性扩展可能不是唯一确定的。
渐近地讲，答案是否定的。只需检查整个输入，Omega(n + m) 就有一个微不足道的下界，拓扑排序会在时间上产生线性扩展 O(n + m)，这不会给任何正确的算法增加渐近成本。