Timeline for Exact Length Problem in a directed graph
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 12, 2012 at 15:59 | comment | added | user26425 | Ok I'll try it at that site next time Thz for your help | |
| Sep 12, 2012 at 15:52 | comment | added | Gerhard Paseman | 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 | |
| Sep 12, 2012 at 15:49 | comment | added | Gerhard Paseman | 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 | |
| Sep 12, 2012 at 15:41 | comment | added | user26425 | thx a lot I think I figure it out! | |
| Sep 12, 2012 at 15:36 | comment | added | Gerhard Paseman | 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 | |
| Sep 12, 2012 at 6:31 | comment | added | user26425 | oh yea,Q<=100000 and T<=10^9 | |
| Sep 12, 2012 at 6:29 | history | asked | user26425 | CC BY-SA 3.0 |