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.

Let $G=(V,E)$ be a weighted directed graph with edge-weights given by linear functions $f_i(x) = ax-b$, $0 < a < 1$, $b > 0$. For a given starting parameter $x_0$, a path from $v_i$ to $v_j$ across edges $e_0, e_1, e_2, ... e_n$ is given a cost of $x_0 - f_n(f_{n-1}(...(f_1(f_0(x_0)))...))$. The problem is to find the center of the graph - the node with the minimal cost to reach any other node.

As an example of this problem, consider a vehicle traversing roads between cities. The vehicle has very poor gas mileage per weight of fuel, so that $x$ represents fuel remaining, and $f_i(x)$ represents the remaining fuel in the tank after traversing the road with $x$ amount of fuel in the tank to start with. The goal is to determine which starting city would allow the smallest possible amount of fuel in the tank to start with.

The only way I can think of is exhaustively testing each node to find the smallest $x_0$ which would reach all other nodes on the graph, and then select the node with the smallest $x_0$. Is there a faster way?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Sounds like you have an all-pairs shortest path problem. I guess there isn't a non-exhaustive way to solve it. The complexity is around $O(|V|^3)$.

share|improve this answer
    
This sounds pretty likely, thanks! –  Foo Barrigno Jul 3 '13 at 16:34

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.