Reachability and distance queries via 2-hop labels

摘要: Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems Internet routing. Some of these applications involve huge yet require fast query answering. We propose a new data structure for representing all distances graph. The is distributed the sense that it may be viewed as assigning labels vertices, such involving vertices u v answered using only v.Our based on 2-hop covers shortest paths, or For cover collection S paths every two v, there path concatenation S. describe an efficient algorithm finding almost optimal given paths. Our approach general can applied directed undirected graphs, exact approximate reachability queries.We study proposed combination theoretical experimental means. implemented our checked size resulting several real-life networks different application areas. experiments show total typically not much larger than network itself, usually considerably smaller explicit representation transitive closure network.