Цикл максимального веса в графе

Учитывая взвешенный граф (направленный или неориентированный), мне нужно найти цикл графа с максимальным весом.

Вес цикла является суммой весов ребер графа. график.

Это может быть любой цикл, не только базовый цикл, для которого мы можем

• найти весь базовый цикл (см. Алгоритмы для идентификации всех основ цикла в неориентированном графе )
• вычислить вес каждого базового цикла и найти максимум

Я мог бы попытаться перечислить все циклы графа, а затем вычислить максимум, но общее количество циклов может быть действительно большим (если граф полный, то любая последовательность вершин, в которой первая и последняя идентичны, является циклом) .

Есть ли у вас идея найти цикл с максимальным весом без перечисления всех циклов?

Если вам нужна гипотеза на графике (например, положительные веса), укажите их.