If you have an undirected, unweighted graph G, and a marked subset of points called 'Firehouses,' is there an O(n+m) algorithm to find every vertex's closes firehouse?
I can only come up with O(n^2) stuff. Although I do like the idea of repeatedly raising the adjacency matrix to a power n, until every vertex has a nonzero entry :P
You could use some sort of parallel breadth first search.
Name:
Anonymous2009-01-30 16:41
Install OpenBSD and read TAOCP.
Name:
Anonymous2009-01-30 17:32
Install Windows and read "Everybody Poops".
Name:
Anonymous2009-01-30 17:37
Install Mac OS X and pretend you can read.
Name:
Anonymous2009-01-30 18:34
Fuck it, get a Wii
Name:
Anonymous2009-01-30 20:36
You didn't even specify what n and m are, so I will assume that m = 2^n, in which case you are wanting a O(2^n) algorithm which is simple to find. Good luck.
Name:
Anonymous2009-01-30 21:53
Call the people living at every vertex, ask them what the closest firehouse is. O(n).
Use a large megaphone to ask everybody all at once. O(1).
Name:
Anonymous2009-01-31 6:38
let the shit burn. O(0)
Name:
Anonymous2009-01-31 7:37
For each firehouse assign the neighbors of that firehouse to it. Then for each firehouse assign the neighbors of the vertices that were assigned to that firehouse in the previous round to it. Repeat until all vertices have been assigned.
That's not good enough. I think I might have gotten it though.
You're not allowed to know which are firehouses until you visit the points so here's what I came up with.
Initialize every vertex's distance to 0.
Begin a standard depth first search on any vertex v.
Until the first firehouse is found, add 1 to the distance of each vertex you have visited.
When the first firehouse is found, keep it's distance to zero, and then continue the depth first search, assigning the distance as the minimum of its parent's distance+1, or any of it's backedges+1.
I think that works in O(n+m) time.
Name:
Anonymous2009-01-31 13:14
>>20
You still haven't defined n or m, so assuming m = 2^n, yes, the algorithm does run in O(n+m) = O(2^n) time.
Name:
Anonymous2009-01-31 13:19
m is the number of edges, n is the number of vertices.
Did >>5 elude you somehow? Do any search you'd like first to find all the fucking firehouses. Do a BFS with a start point at each firehouse, keep track of origin (optional), and assign nodes to houses as you encounter them. Oh, and of course, don't keep your graph in a god damn adjacency matrix. HTH, Now stop trolling.