optimal way to calculate all nodes at distance less than k from m given nodes
I can think of two non-asymptotic (I believe) optimizations:
- If you're done with BFS from one of the subset nodes, delete all nodes that have distance > k from it
- Start with the two nodes in the subset whose distance is largest to get the smallest possible leftover graph
Of course this doesn't help if k is large (close to n), I have no idea in that case. I am positive however that k/d trees are not applicable to general graphs :)