文章基本信息

标题：Dispersion on Trees
本地全文：下载
作者：Pawel Gawrychowski ; Nadav Krasnopolsky ; Shay Mozes 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：87
页码：40:1-40:13
DOI：10.4230/LIPIcs.ESA.2017.40
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：parametric search; dispersion; k-center; dynamic programming