有没有一个有效的算法可以从一个偏序的单个transitive reduction创建linear extension？
更新：实际上，部分顺序是已知的我也知道给定偏序的time complexity of computing a transitive reduction。我想知道的是：给定一个偏序和一个线性扩展，可以减少时间复杂度吗？
最佳答案
渐近地说，答案是否定的，欧米茄（n+m）有一个很小的下界，因为它只需要检查整个输入，而拓扑排序在时间O（n+m）上产生一个线性扩展，这不会增加任何正确算法的渐近代价。
关于algorithm - 偏序线性扩展的传递减少，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32624542/