DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2020.27

Efficient Labeling for Reachability in Directed Acyclic Graphs

Authors: Maciej Dulęba, Paweł Gawrychowski, and Wojciech Janczewski

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

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.

Cite as

Maciej Dulęba, Paweł Gawrychowski, and Wojciech Janczewski. Efficient Labeling for Reachability in Directed Acyclic Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{duleba_et_al:LIPIcs.ISAAC.2020.27,
  author =	{Dul\k{e}ba, Maciej and Gawrychowski, Pawe{\l} and Janczewski, Wojciech},
  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 =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.27},
  URN =		{urn:nbn:de:0030-drops-133710},
  doi =		{10.4230/LIPIcs.ISAAC.2020.27},
  annote =	{Keywords: informative labeling scheme, reachability, DAG}
}

Search Results

Documents authored by Janczewski, Wojciech

Efficient Labeling for Reachability in Directed Acyclic Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message