Если вы используете термины из упомянутой вами бумаги и определяете остовное дерево ориентированного графа как дерево с корнем в вершине r, имеющее уникальный путь от r до любой другой вершины, то:
Очевидно, что наихудший случай при направленномГраф имеет наибольшее количество связующих деревьев, является полным графом (для любой пары есть a-> b и b-> a ребра).Если мы «забудем» о направлениях, то получим n ^ {n-2} остовных деревьев, как в случае неориентированных графов.Для любого из этих связующих деревьев у нас есть n опций для выбора корня, и этот выбор однозначно определяет направления ребер, которые мы должны использовать.Нетрудно видеть, что все деревья, которые мы получаем, являются уникальными и не имеют никаких других вариантов.Таким образом, мы получаем n ^ {n-1} остовных деревьев.Строгое доказательство займет время, я надеюсь, что достаточно простого объяснения.
Таким образом, эта задача займет экспоненциальное время в зависимости от числа вершин в худшем случае.Учитывая размер вывода (все связующие деревья), я делаю вывод, что для произвольного графа алгоритм не может быть значительно быстрее и лучше.Я думаю, вам нужно как-то переформулировать исходную проблему, чтобы не охватывать все связующие деревья, и поиск может быть необходим только по некоторым критериям.