2026-08-05T23:40:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17344 2024-03-06T10:59:31Z ddc:004 open_access

Shortest Beer Path Queries in Interval Graphs Das, Rathish He, Meng Kondratovsky, Eitan Munro, J. Ian Naredla, Anurag Murty Wu, Kaiyu Beer Path Interval Graph Our interest is in paths between pairs of vertices that go through at least one of a subset of the vertices known as beer vertices. Such a path is called a beer path, and the beer distance between two vertices is the length of the shortest beer path. We show that we can represent unweighted interval graphs using 2n log n + O(n) + O(|B|log n) bits where |B| is the number of beer vertices. This data structure answers beer distance queries in O(log^ε n) time for any constant ε > 0 and shortest beer path queries in O(log^ε n + d) time, where d is the beer distance between the two nodes. We also show that proper interval graphs may be represented using 3n + o(n) bits to support beer distance queries in O(f(n)log n) time for any f(n) ∈ ω(1) and shortest beer path queries in O(d) time. All of these results also have time-space trade-offs. Lastly we show that the information theoretic lower bound for beer proper interval graphs is very close to the space of our structure, namely log(4+2√3)n - o(n) (or about 2.9 n) bits. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rathish Das and Meng He and Eitan Kondratovsky and J. Ian Munro and Anurag Murty Naredla and Kaiyu Wu 2022 Is Part Of LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2022.59 urn:nbn:de:0030-drops-173442 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.59 eng https://creativecommons.org/licenses/by/4.0/legalcode