Re: overall-longest-possible-path problem

In article <d4ausi$nsi$1@xxxxxxxxxxxx>, Alexander Landa <sorry@xxxxxxx> wrote:
>i'm looking for some research papers and algorithms for solving
>"overall-longest-possible path" problem, that is finding lonegst
>path between all pairs of nodes in graph (not digraph!) which can
>contain cycles (multiple vertices but only singe edges) in solution.

I can't help much, unfortunately, except to suggest that what you're looking
for is often called a "longest trail" rather than a "longest path."

Of course, as someone else mentioned, if you can hit *every* edge then
you have an "Eulerian trail," about which there is much literature,
but I don't know how you would maximize the length of a trail if there
is no Eulerian trail.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.