License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.59
URN: urn:nbn:de:0030-drops-173442
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17344/
Go to the corresponding LIPIcs Volume Portal

Das, Rathish ; He, Meng ; Kondratovsky, Eitan ; Munro, J. Ian ; Naredla, Anurag Murty ; Wu, Kaiyu

Shortest Beer Path Queries in Interval Graphs

pdf-format:
LIPIcs-ISAAC-2022-59.pdf (0.9 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{das_et_al:LIPIcs.ISAAC.2022.59,
  author =	{Das, Rathish and He, Meng and Kondratovsky, Eitan and Munro, J. Ian and Naredla, Anurag Murty and Wu, Kaiyu},
  title =	{{Shortest Beer Path Queries in Interval Graphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{59:1--59:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17344},
  URN =		{urn:nbn:de:0030-drops-173442},
  doi =		{10.4230/LIPIcs.ISAAC.2022.59},
  annote =	{Keywords: Beer Path, Interval Graph}
}

Keywords: Beer Path, Interval Graph
Collection: 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Issue Date: 2022
Date of publication: 14.12.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI