LIPIcs.ESA.2017.40.pdf
- Filesize: 476 kB
- 13 pages
Document
Dispersion on Trees
Authors
-
Part of:
Volume:
25th Annual European Symposium on Algorithms (ESA 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-09-01
Cite As Get BibTex
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)
https://doi.org/10.4230/LIPIcs.ESA.2017.40
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.
Subject Classification
Keywords
- parametric search
- dispersion
- k-center
- dynamic programming
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
R.I. Becker, S.R. Schach, and Y. Perl. A shifting algorithm for min-max tree partitioning. J. ACM, 29(1):56-67, 1982.
-
B.K. Bhattacharya and M.E. Houle. Generalized maximum independent sets for trees. In CATS, pages 17-25, 1997.
-
B.K. Bhattacharya and M.E. Houle. Generalized maximum independent sets for trees in subquadratic time. In ISAAC, pages 435-445, 1999.
-
M.R. Brown and R.E. Tarjan. Design and analysis of a data structure for representing sorted lists. SIAM Journal on Computing, 9(3):594-614, 1980.
-
Richard Cole. Slowing down sorting networks to obtain faster sorting algorithms. J. ACM, 34(1):200-208, 1987.
-
G.N. Frederickson. Optimal algorithms for partitioning trees and locating p-centers in trees. Technical Report CSD-TR-1029, Purdue University, 1990.
-
G.N. Frederickson. Optimal algorithms for tree partitioning. In SODA, pages 168-177, 1991.
-
G.N. Frederickson. Parametric search and locating supply centers in trees. In WADS, pages 299-319, 1991.
-
G.N. Frederickson and D.B. Johnson. Finding k-th paths and p-centers by generating and searching good data structures. J. Algorithms, 4(1):61-80, 1983.
-
Scott Huddleston and Kurt Mehlhorn. A new data structure for representing sorted lists. Acta Inf., 17:157-184, 1982.
-
N. Megiddo and A. Tamir. New results on the complexity of p-center problems. SIAM J. Computing, 12(3):751-758, 1983.
-
N. Megiddo, A. Tamir, E. Zemel, and R. Chandrasekaran. An O(n log² n) algorithm for the k-th longest path in a tree with applications to location problems. SIAM J. Computing, 10(2):328-337, 1981.
-
Y. Perl and S.R. Schach. Max-min tree partitioning. J. ACM, 28(1):5-15, 1981.
-
D.B. Shmoys, É. Tardos, and K. Aardal. Approximation algorithms for facility location problems. In STOC, pages 265-274, 1997.
-
D.D. Sleator and R.E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362–391, 1983.
-
V.V. Vazirani. Approximation Algorithms. Springer, 2003.