DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2017.40

Dispersion on Trees

Authors: Pawel Gawrychowski, Nadav Krasnopolsky, Shay Mozes, and Oren Weimann

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract

In the k-dispersion problem, we need to select k nodes of a given graph so as to maximize the minimum distance between any two chosen nodes. This can be seen as a generalization of the independent set problem, where the goal is to select nodes so that the minimum distance is larger than 1. We design an optimal O(n) time algorithm for the dispersion problem on trees consisting of n nodes, thus improving the previous O(n log n) time solution from 1997. We also consider the weighted case, where the goal is to choose a set of nodes of total weight at least W. We present an O(n log^2n) algorithm improving the previous O(n log^4 n) solution. Our solution builds on the search version (where we know the minimum distance lambda between the chosen nodes) for which we present tight Theta(n log n) upper and lower bounds.

Cite as

Pawel Gawrychowski, Nadav Krasnopolsky, Shay Mozes, and Oren Weimann. Dispersion on Trees. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 40:1-40:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:LIPIcs.ESA.2017.40,
  author =	{Gawrychowski, Pawel and Krasnopolsky, Nadav and Mozes, Shay and Weimann, Oren},
  title =	{{Dispersion on Trees}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{40:1--40:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.40},
  URN =		{urn:nbn:de:0030-drops-78438},
  doi =		{10.4230/LIPIcs.ESA.2017.40},
  annote =	{Keywords: parametric search, dispersion, k-center, dynamic programming}
}

Search Results

Documents authored by Krasnopolsky, Nadav

Dispersion on Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message