Keep It Simple, Stupid | |
PerlMonks |
comment on |
( [id://3333]=superdoc: print w/replies, xml ) | Need Help?? |
This problem in graph theory is known as the graph center problem.
So here's a cop-out solution using Graph.pm:
<Reveal this spoiler or all in this thread>
I'm sure there should be a more efficient algorithm for graph center than computing all pairs shortest paths (although it makes a difference if the bottleneck is computing Levenshtein distance or dealing with the big graph), but this is a starting point. Especially interesting would be an algorithm that explored the graph in an "on-line" fashion to avoid precomputing all the pairwise distances. BTW, Graph.pm does offer a center_vertices method for the APSP object, but it appears to be broken (at least in my version of the module). blokhead In reply to Re: Challenge: Find median string in a list
by blokhead
|
|