2
Я хочу знать, существует ли эффективный алгоритм для вычисления минимального покрытия пути в ациклическом графике с прямым преобразованием. Не путайте минимальную «дорожку» с «вершиной-непересекающейся дорожкой». Для последнего я знаю эффективный алгоритм с использованием Максимального совпадения соответствующего двухпартийного графа. Но это относится только к вершине-дизъюнктному случаю. Можно ли смягчить тот же алгоритм, чтобы получить ответ на покрытие пути, когда каждую вершину можно посещать несколько раз?Минимальная ширина пути в DAG
Возможно, я ошибаюсь, но не будет ли транзитивное замыкание работать в O (N^3)? Будет ли это временной сложностью вашего алгоритма? Потому что я искал алгоритм O (N * M) так же, как непересекающийся случай. – divanshu
@divanshu: Я не знаю, существует ли алгоритм O (N * M) для этого случая. Что касается временной сложности этого алгоритма, вы можете получить транзитивное замыкание в O (N * M), как описано [здесь] (http://cs.stackexchange.com/questions/7231/efficient-algorithm-for-retrieving-the- транзитивен-замыкание в своем-направленного ациклического). Но после этого вы вычислите двухстороннее соответствие для плотного графа; алгоритм Хопкрофта-Карпа со сложностью O (V^2.5) - лучший практический алгоритм, который я знаю; что дает общую сложность O (V^2,5). Или вы можете использовать подход, основанный на быстром умножении матрицы с сложностью O (V^2.376). –