Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Assume we have a path in an undirected cyclic weighted graph. Assuming we have an engine that can find a path from node A to node B in such a graph, is there an easy way/algorithm to figure out if the given path from A to B is at least X% better than any other disjoint path from A to B? By disjoint I mean two paths may not share any edges.

share|cite|improve this question
    
When you mean cyclic, do you mean it's a cycle? – mixedmath Oct 7 '11 at 23:14
    
I mean it has cycles. – Schultz9999 Oct 7 '11 at 23:17
    
Perhaps this paper might be of use: dl.acm.org/citation.cfm?id=78636 – Joseph Malkevitch Oct 8 '11 at 22:24
    
@JosephMalkevitch: we already have A* based search engine. – Schultz9999 Oct 10 '11 at 22:46

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.