Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a directed graph that consist of N^2 vertices (like a square) and each vertex is connected to at most 1 node (not bidirectional) and every connections have length 1. There are no cycles in the graph. Now I have Q requests , each given a node, return the node that has exactly T distance between the given node.If no such node exists,return the node with largest distance.

BFS for every vertices works, but it sucks when N=1000,and T<=10000. Is there exists a method that works with (N^2 log N) time?

share|improve this question
    
oh yea,Q<=100000 and T<=10^9 –  user26425 Sep 12 '12 at 6:31
    
Use a structure with roughly logN entries per node. The ith entry for node v contains (a pointer to) the node at distance 2^i from v. Gerhard "You Figure Out The Rest" Paseman, 2012.09.12 –  Gerhard Paseman Sep 12 '12 at 15:36
    
thx a lot I think I figure it out! –  user26425 Sep 12 '12 at 15:41
    
If you are cramped for space, but know the nodes in the Q queries and know that the size of that set is small, you can try building up the the database for each node in Q and stop when you have processed the whole list. Worst case involves making the table for the whole graph, but expected behavior can save a lot of time and space. Gerhard "Not To Mention Programming Effort" Paseman, 2012.09.12 –  Gerhard Paseman Sep 12 '12 at 15:49
    
Also, while this is a nice problem, it is out of scope for this site. For similar questions, try the stackexchange sites for math and computer science. Good Luck. Gerhard "Ask Me About System Design" Paseman, 2012.09.12 –  Gerhard Paseman Sep 12 '12 at 15:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.