11
$\begingroup$

Let $G(V, E)$ be a edge-weighted directed connected graph and $v_1, \dots, v_n \in V$ be some vertices. Let $d(a, b)$ denote the length of the shortest path from $a$ to $b$, for $a,b \in V$.

I need to find a vertex $v \in V$ such that $$\sum_{i=1}^n d(v_i, v)^2$$ is minimal. What is the most time-efficient algorithm to solve this problem? Could I do any better than computing shortest paths from all $v_i$ to all other vertices in the graph?

Real-world example: $n$ friends are looking for a place for a meeting.

This is similar to closeness centrality, but here I have a sum of squared distances rather than sum of distances.

$\endgroup$
  • $\begingroup$ You are dealing with directed weighted graphs (very general), and it makes it very difficult to find a fast algorithm, unless there is some other constraint such as Euclidean distance, metric space or some other properties? $\endgroup$ – orezvani May 11 '16 at 5:28
  • $\begingroup$ @emab No special constraints, unfortunately :(... $\endgroup$ – vojta May 11 '16 at 6:34
  • $\begingroup$ Why not using parallel algorithms? $\endgroup$ – orezvani May 11 '16 at 6:59
  • $\begingroup$ @emab Which particular algorithm do you mean? Or just compute shortest paths in parallel threads? $\endgroup$ – vojta May 11 '16 at 12:18
  • 1
    $\begingroup$ Without an embedding in $\mathbb{R}^2$, you probably won't be able to get any better than checking all possible paths as you mentioned. $\endgroup$ – koverman47 Jul 20 '18 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.