Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Hi this is the second last problem in my text book got to do with graphs, and i was wondering if anyone could help me with my pre-exam prep. Specifically, i was having trouble visualizing an algorithm that is $O(n+m)$.

For a given graph $G=(V,E)$ and an edge $e\in E$, design an $O(n+m)$-time algorithm to find, if it exists, the shortest cycle that contains e.

TIA

share|improve this question
    
What have you tried? How would you find out whether some cycle containing $e$ exist, without necessarily finding the shortest cycle? –  Henning Makholm Sep 23 '12 at 15:27
    
uh, well i was kind of having trouble starting. I'm grappling with the idea that you could probably have the algorithm follow some method of Depth First Search? –  AlanTuring Sep 24 '12 at 1:06
    
That's a good start. Not the right solution, but a good start. Try writing down in some more detail how that's going to work. –  Henning Makholm Sep 24 '12 at 12:56
    
do you think an algorithm like this would be correct? siafoo.net/algorithm/10 –  AlanTuring Sep 25 '12 at 0:00
    
No, that's for linearly linked list. Try editing the question to see how far your depth-first idea gets you. –  Henning Makholm Sep 25 '12 at 11:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.