Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Re: Challenge: Find median string in a list

by blokhead (Monsignor)
on Jul 04, 2007 at 19:18 UTC ( #624930=note: print w/replies, xml ) Need Help??


in reply to Challenge: Find median string in a list

This problem in graph theory is known as the graph center problem. So here's a cop-out solution using Graph.pm:

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

Replies are listed 'Best First'.
Re^2: Challenge: Find median string in a list
by Limbic~Region (Chancellor) on Jul 05, 2007 at 01:05 UTC
    blokhead,
    This solution took nearly 5 hours (compared to 0.28 seconds). I am not sure how well it would have done if center_vertices would have worked.

    Cheers - L~R

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://624930]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (4)
As of 2020-04-10 09:06 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    The most amusing oxymoron is:
















    Results (49 votes). Check out past polls.

    Notices?