Document Open Access Logo

Shortest Beer Path Queries in Outerplanar Graphs

Authors Joyce Bacic, Saeed Mehrabi, Michiel Smid

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.62.pdf
  • Filesize: 0.86 MB
  • 16 pages

Document Identifiers

Author Details

Joyce Bacic
  • Carleton University, Ottawa, Canada
Saeed Mehrabi
  • University of Massachusetts Lowell, MA, USA
Michiel Smid
  • Carleton University, Ottawa, Canada

Funding

  • Bacic, Joyce: Supported by an NSERC Undergraduate Student Research Award.
  • Smid, Michiel: Supported by NSERC

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.62

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).

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • shortest paths
  • outerplanar graph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. N. Alon and B. Schieber. Optimal preprocessing for answering on-line product queries. Technical Report 71/87, Tel-Aviv University, 1987. Google Scholar
  2. M. A. Bender and M. Farach-Colton. The LCA problem revisited. In Proceedings of the 4th Latin American Symposium on Theoretical Informatics, volume 1776 of Lecture Notes in Computer Science, pages 88-94, Berlin, 2000. Springer-Verlag. Google Scholar
  3. T. M. Chan, M. He, J. I. Munro, and G. Zhou. Succinct indices for path minimum, with applications. Algorithmica, 78(2):453-491, 2017. Google Scholar
  4. B. Chazelle. Computing on a free tree via complexity-preserving mappings. Algorithmica, 2:337-361, 1987. Google Scholar
  5. H. Djidjev, G. E. Pantziou, and C. D. Zaroliagis. Computing shortest paths and distances in planar graphs. In Automata, Languages and Programming, 18th International Colloquium, ICALP91, volume 510 of Lecture Notes in Computer Science, pages 327-338. Springer, 1991. Google Scholar
  6. D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM J. Comput., 13(2):338-355, 1984. Google Scholar
  7. S. Pettie. An inverse-Ackermann type lower bound for online minimum spanning tree verification. Combinatorica, 26(2):207-230, 2006. Google Scholar
  8. M. Thorup. Parallel shortcutting of rooted trees. Journal of Algorithms, 32:139-159, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact