Patent ID: 8296327

Claim:
One or more computer-readable storage media storing instructions which, when executed by one or more processors disposed in an electronic device, perform a method for computing short paths in a scale-free directed graph, the method comprising the steps of: identifying by the one or more processors one or more hubs in the graph where the graph represents a communication network, the hubs being high-degree vertices; pre-computing data structures for each of the one of more hubs, each of the pre-computed data structures comprising an in-tree and an out-tree, the in-tree including shortest paths directed from vertices in the graph to a given hub, the out-tree including shortest paths directed from the given hub to vertices in the graph, the pre-computing being performed prior to processing of a path query on the graph; storing the pre-computed data structures; when during the processing of the path query, an exact shortest path is not found, generating an upper bound on the exact shortest path; once the upper bound is determined, performing a secondary path finding technique in the neighborhood of the short path in order to find the exact shortest path.