Extended Longest Path problem
January 3, 2010 Leave a comment
These are slides from a talk on the Longest Path Problem at the Penn State Theory seminar.
In the Longest Path Problem, we are given an undirected graph, G =(V,E), and integer , and are asked to find out whether or not there exists a simple path of length k in G.
The Extended Longest Path Problem is a variant of the above. Here, we are asked to find out all pairs of vertices that have a simple path of length k between them.
The Longest Path problem is NP-complete.
The talk deals with 3 approaches to solving the Extended Longest Path Problem:-
1. Method of Random Orientations
All three methods use randomization.