# Shortest-Path Queries for Complex Networks: Exploiting Low Tree-width Outside the Core

Takuya Akiba, Christian Sommer, and Ken-ichi Kawarabayashi
EDBT 2012 - 15th International Conference on Extending Database Technology (pp. 144-155)

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.

Our main contributions are efficient algorithms and data structures on three different levels. First, we provide two new methods for graphs with small but not necessarily constant tree-width. Our methods achieve new tradeoffs between space and query time. Second, we present an improved tree-decomposition-based method for complex networks, utilizing the methods for graphs with small tree-width. Third, we extend our method to handle the highly inter-connected core with existing exact and approximate methods.

We evaluate our algorithms both analytically and experimentally. We prove that our algorithms for low-tree-width graphs achieve improved tradeoffs between space and query time. Our experiments on several real-world complex networks further confirm the efficiency of our methods: Both the exact and the hybrid method have faster preprocessing and query times than existing methods. The hybrid method in particular provides an improved tradeoff between space and accuracy.


author    = {Takuya Akiba
and Christian Sommer
and {Ken-ichi} Kawarabayashi},
title     = {Shortest-Path Queries for Complex Networks:
Exploiting Low Tree-width Outside the Core},
booktitle = {15th International Conference on
Extending Database Technology (EDBT)},
year      = {2012},
pages     = {144--155},
url       = {http://dx.doi.org/10.1145/2247596.2247614},
doi       = {10.1145/2247596.2247614},
}


Official version
Local version (214.9 KB)
Slides (2.2 MB)

HomePublications → Shortest-Path Queries for Complex Networks: Exploiting Low Tree-width Outside the Core