[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:1.9.2.18) 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)?
--
T.