Алгоритм поиска самой длинной цепи в неориентированном графе

[Zeddikus]

Дан неориентированный граф с длинами рёбер. Требуется найти (за приемлемое время) в нём самую длинную цепочку.
Граф небольшой (~10 вершин), однако мне кажется, что здесь не подойдёт алгоритм перебора.
С другой стороны, я думаю, что такой алгоритм, как выбор самого длинного ребра и присоединение к сформировавшейся цепочке самого длинного ребра с одного из концов, пока это возможно, а также такой алгоритм, как выкидывание самого короткого ребра (если не нарушается связность) до тех пор, пока граф не станет эйлеровым (0-2 вершины нечётной степени) являются приближёнными, а не точными.

Пробовал выкидывать самые короткие цепочки между вершинами нечётной степени до тех пор, пока граф не станет эйлеровым, но и для такого алгоритма мне не удалось найти строгое доказательство.

[Zeddikus]

В принципе, эту задачу можно свести к задаче о поиске самой длинной цепочки в обычном графе (т.к. ребро с длиной можно заменить на необходимое количество единичных рёбер), а она NP-трудная, значит решается перебором.

[Null]

Для каждого подмножества вершин и каждой вершины из этого подмножества найдите длиннейшую цепочку начинающуюся в этой вершине.

[Sender]

Null в сообщении #1391285 писал(а):

Для каждого подмножества вершин и каждой вершины из этого подмножества найдите длиннейшую цепочку начинающуюся в этой вершине.

Наверное, не помешает уточнить:
Для каждого подмножества вершин и каждой вершины из этого подмножества найдите длиннейшую цепочку, начинающуюся в этой вершине, целиком лежащую в этом подмножестве.