Shortest-path queries for complex networks
Takuya Akiba, Christian Sommer, Ken‐ichi Kawarabayashi · 2012
We present new and improved methods for efficient shortest-path query processing. Our methods are tailored to work for two specific classes of graphs: graphs with small tree-width and complex networks. Seemingly unrelated at first glance, these two classes of graphs have some commonalities: complex networks are known to have a core--fringe structure with a dense core and a tree-like fringe.