DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2021.13

O'Reach: Even Faster Reachability in Large Graphs

Authors: Kathrin Hanauer, Christian Schulz, and Jonathan Trummer

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

Abstract

One of the most fundamental problems in computer science is the reachability problem: Given a directed graph and two vertices s and t, can s reach t via a path? We revisit existing techniques and combine them with new approaches to support a large portion of reachability queries in constant time using a linear-sized reachability index. Our new algorithm O'Reach can be easily combined with previously developed solutions for the problem or run standalone. In a detailed experimental study, we compare a variety of algorithms with respect to their index-building and query times as well as their memory footprint on a diverse set of instances. Our experiments indicate that the query performance often depends strongly not only on the type of graph, but also on the result, i.e., reachable or unreachable. Furthermore, we show that previous algorithms are significantly sped up when combined with our new approach in almost all scenarios. Surprisingly, due to cache effects, a higher investment in space doesn't necessarily pay off: Reachability queries can often be answered even faster than single memory accesses in a precomputed full reachability matrix.

Cite as

Kathrin Hanauer, Christian Schulz, and Jonathan Trummer. O'Reach: Even Faster Reachability in Large Graphs. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 13:1-13:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hanauer_et_al:LIPIcs.SEA.2021.13,
  author =	{Hanauer, Kathrin and Schulz, Christian and Trummer, Jonathan},
  title =	{{O'Reach: Even Faster Reachability in Large Graphs}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{13:1--13:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.13},
  URN =		{urn:nbn:de:0030-drops-137856},
  doi =		{10.4230/LIPIcs.SEA.2021.13},
  annote =	{Keywords: Reachability, Static Graphs, Graph Algorithms, Reachability Index, Algorithm Engineering}
}

Search Results

Documents authored by Trummer, Jonathan

O'Reach: Even Faster Reachability in Large Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message