Publication
Top-k Shortest Paths in Directed Labeled Multigraphs
Sven Hertling; Markus Schröder; Christian Jilek; Andreas Dengel
In: Harald Sack; Stefan Dietze; Anna Tordai; Christoph Lange (Hrsg.). The Semantic Web: ESWC 2016 Challenges. Extended Semantic Web Conference (ESWC-16), 13th Extended Semantic Web Conference, May 29 - June 2, Heraklion, Greece, Springer, 2016.
Abstract
A top-k shortest path algorithm finds the k shortest paths of a given graph ordered by length.
Interpreting graphs as RDF may lead to additional constraints, such as special loop restrictions or path patterns.
Thus, traditional algorithms such as the ones by Dijkstra, Yen or Eppstein cannot be applied without further ado.
We therefore implemented a solution method based on Eppstein's algorithm which is thoroughly discussed in this paper.
Using this method we were able to solve all tasks of the ESWC 2016 Top-k Shortest Path Challenge while achieving only moderate overhead compared to the original version.
However, we also identified some potential for improvements.
Additionally, a concept for embedding our algorithm into a SPARQL endpoint is provided.
Projekte
MOM - Multimedia Opinion Mining,
PRO-OPT - PRO-OPT - Big Data in Smart Ecosystems,
supSpaces - Semantische Support-Wissensräume für agiles Wissensmanagement im 3rd - Level Support,
CoMem - Corporate Memory
PRO-OPT - PRO-OPT - Big Data in Smart Ecosystems,
supSpaces - Semantische Support-Wissensräume für agiles Wissensmanagement im 3rd - Level Support,
CoMem - Corporate Memory