License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.27
URN: urn:nbn:de:0030-drops-133710
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13371/
Go to the corresponding LIPIcs Volume Portal

Dulęba, Maciej ; Gawrychowski, Paweł ; Janczewski, Wojciech

Efficient Labeling for Reachability in Directed Acyclic Graphs

pdf-format:
LIPIcs-ISAAC-2020-27.pdf (0.6 MB)

Abstract

We consider labeling nodes of a directed graph for reachability queries. A reachability labeling scheme for such a graph assigns a binary string, called a label, to each node. Then, given the labels of nodes u and v and no other information about the underlying graph, it should be possible to determine whether there exists a directed path from u to v. By a simple information theoretical argument and invoking the bound on the number of partial orders, in any scheme some labels need to consist of at least n/4 bits, where n is the number of nodes. On the other hand, it is not hard to design a scheme with labels consisting of n/2+?(log n) bits. In the classical centralised setting, where a single data structure is stored as a whole, Munro and Nicholson designed a structure for reachability queries consisting of n²/4+o(n²) bits (which is optimal, up to the lower order term). We extend their approach to obtain a scheme with labels consisting of n/3+o(n) bits.

BibTeX - Entry

@InProceedings{dulba_et_al:LIPIcs:2020:13371,
  author =	{Maciej Dulęba and Pawe{\l} Gawrychowski and Wojciech Janczewski},
  title =	{{Efficient Labeling for Reachability in Directed Acyclic Graphs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13371},
  URN =		{urn:nbn:de:0030-drops-133710},
  doi =		{10.4230/LIPIcs.ISAAC.2020.27},
  annote =	{Keywords: informative labeling scheme, reachability, DAG}
}

Keywords: informative labeling scheme, reachability, DAG
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

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