1 Search Results for "Bacic, Joyce"


Document
Shortest Beer Path Queries in Outerplanar Graphs

Authors: Joyce Bacic, Saeed Mehrabi, and Michiel Smid

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)


Abstract
A beer graph is an undirected graph G, in which each edge has a positive weight and some vertices have a beer store. A beer path between two vertices u and v in G is any path in G between u and v that visits at least one beer store. We show that any outerplanar beer graph G with n vertices can be preprocessed in O(n) time into a data structure of size O(n), such that for any two query vertices u and v, (i) the weight of the shortest beer path between u and v can be reported in O(α(n)) time (where α(n) is the inverse Ackermann function), and (ii) the shortest beer path between u and v can be reported in O(L) time, where L is the number of vertices on this path. Both results are optimal, even when G is a beer tree (i.e., a beer graph whose underlying graph is a tree).

Cite as

Joyce Bacic, Saeed Mehrabi, and Michiel Smid. Shortest Beer Path Queries in Outerplanar Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 62:1-62:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{bacic_et_al:LIPIcs.ISAAC.2021.62,
  author =	{Bacic, Joyce and Mehrabi, Saeed and Smid, Michiel},
  title =	{{Shortest Beer Path Queries in Outerplanar Graphs}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{62:1--62:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.62},
  URN =		{urn:nbn:de:0030-drops-154950},
  doi =		{10.4230/LIPIcs.ISAAC.2021.62},
  annote =	{Keywords: shortest paths, outerplanar graph}
}
  • Refine by Author
  • 1 Bacic, Joyce
  • 1 Mehrabi, Saeed
  • 1 Smid, Michiel

  • Refine by Classification
  • 1 Theory of computation → Data structures design and analysis

  • Refine by Keyword
  • 1 outerplanar graph
  • 1 shortest paths

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021