I have an undirected, unweighted graph and I want to find the node that has the smallest maximum distance to the other nodes in the graph. Pretty much, I just want to find the center of the graph.
I tried an O(N*(N+E)) approach by finding the maximum distance from every single node, and then taking the smallest one. I was wondering if there is any algorithm faster than O(N*(N+E)) to do this job.
You could run BFS from all nodes in parallel, one depth at a time. Then you can stop when one BFS finishes and don't need to finish the others. Still O(N*(N+E)) but might be faster, depending on your data.