DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2018.56

On Counting Oracles for Path Problems

Authors: Ivona Bezáková and Andrew Searns

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract

We initiate the study of counting oracles for various path problems in graphs. Distance oracles have gained a lot of attention in recent years, with studies of the underlying space and time tradeoffs. For a given graph G, a distance oracle is a data structure which can be used to answer distance queries for pairs of vertices s,t in V(G). In this work, we extend the set up to answering counting queries: for a pair of vertices s,t, the oracle needs to provide the number of (shortest or all) paths from s to t. We present O(n^{1.5}) preprocessing time, O(n^{1.5}) space, and O(sqrt{n}) query time algorithms for oracles counting shortest paths in planar graphs and for counting all paths in planar directed acyclic graphs. We extend our results to other graphs which admit small balanced separators and present applications where our oracle improves the currently best known running times.

Cite as

Ivona Bezáková and Andrew Searns. On Counting Oracles for Path Problems. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 56:1-56:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bezakova_et_al:LIPIcs.ISAAC.2018.56,
  author =	{Bez\'{a}kov\'{a}, Ivona and Searns, Andrew},
  title =	{{On Counting Oracles for Path Problems}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{56:1--56:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.56},
  URN =		{urn:nbn:de:0030-drops-100042},
  doi =		{10.4230/LIPIcs.ISAAC.2018.56},
  annote =	{Keywords: Counting oracle, Path problems, Shortest paths, Separators}
}

Search Results

Documents authored by Searns, Andrew

On Counting Oracles for Path Problems

Abstract

Cite as

Thanks for your feedback!

Could not send message