[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Longest path algorithm in igraph?

From: Tamas Nepusz
Subject: Re: [igraph] Longest path algorithm in igraph?
Date: Mon, 18 Jul 2011 12:39:32 +0200
User-agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv: Gecko/20110617 Lightning/1.0b2 Thunderbird/3.1.11

> I know that the longest path problem is NP-complete, but I was
> wondering whether there exist any approximate optimization techniques
> (like, for instance, on modularity maximization for community
> detection, which is also NP-complete).
There are approximation techniques for this problem, e.g.:

Karger et al: On approximating the longest path in a graph. Algorithmica
18(1):82-98, 1997.

> As a matter of fact, I am interested in determining pairs of
> vertices (let's say in a simple undirected graph) which are joined
> together by (possibly multiple) paths having the same length (and
> finding this unique path length for each pair of such vertices).
I'm not sure I understand completely what you mean; do you mean that you are
looking for a pair of vertices (u, v) such that all the *simple* paths from
u to v (simple meaning that it may pass through any vertex only once) are of
equal length (and this would be achieved by checking whether the length of
the shortest path from u to v is the same as the length of the longest path
from u to v)?


reply via email to

[Prev in Thread] Current Thread [Next in Thread]