我想知道是否存在一种有效的算法来计算有向无环图中的最小路径覆盖。请不要将最小“路径覆盖”与“顶点不相交路径覆盖”混淆。对于后者，我知道一种使用相应二分图的最大匹配的有效算法。但这仅适用于顶点不相交的情况。当每个顶点可以被多次访问时，是否可以放宽相同的算法以获得路径覆盖的答案？
问问题
2304 次
1 回答
3
是的，可以根据需要放宽相同的算法。只需计算原始图的传递闭包。
您可以在“通过 König 定理证明”部分的 Wikipedia 文章“Dilworth 定理”中找到完整算法的解释。
于 2013-06-10T10:00:27.233 回答