我想知道是否存在一种有效的算法来计算有向无环图中的最小路径覆盖。请不要将最小“路径覆盖”与“顶点不相交的路径覆盖”混淆。对于后者，我知道使用相应二分图的匹配最大化的有效算法。但这仅适用于顶点不相交的情况。当每个顶点可以多次访问时，是否可以放宽同样的算法以获得路径覆盖的答案？
1个回答
3
是的，同样的算法可以根据您的要求进行放宽。只需计算原图的传递闭包即可。
您可以在维基百科“Dilworth定理”文章中找到完整算法的解释，在“通过König定理的证明”部分。
- Evgeny Kluev
2
我可能错了，但是传递闭包不是以O(N^3)的时间复杂度运行吗？这是否是您算法的时间复杂度？因为我正在寻找一个与不相交情况类似的O(N*M)算法。 - divanshu
@divanshu：我不知道这种情况下是否存在O(NM)算法。至于该算法的时间复杂度，您可以按照这里所述以O(NM)的时间复杂度获取传递闭包。但是在此之后，您将为密集图计算二分图匹配；Hopcroft-Karp算法具有O(V^2.5)的复杂度，是我所知道的最好的实用算法；这将给出总体复杂度O(V^2.5)。或者，您可以使用基于快速矩阵乘法的方法，其复杂度为O(V^2.376)。 - Evgeny Kluev
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接