An $O(n\log n)$-Time Algorithm for the $k$-Center Problem in Trees

DOI10.1137/18M1196522zbMath1489.68211arXiv1705.02752OpenAlexW3146642513MaRDI QIDQ5858648

Haitao Wang, Jing-Ru Zhang

Publication date: 14 April 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1705.02752

zbMATH Keywords

algorithmstreescomputational geometry\(k\)-centerfacility locations

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80)

Related Items

Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows, The two-center problem of uncertain points on a real line

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• One-dimensional \(k\)-center on uncertain data
• Efficient algorithms for the one-dimensional \(k\)-center problem
• Optimal slope selection via expanders
• Sorting in \(c \log n\) parallel steps
• Optimal slope selection via cuttings
• A note on computing the center of uncertain data on the real line
• Some variations on constrained minimum enclosing circle problem
• Approximating points by a piecewise linear function
• A note on searching line arrangements and applications
• Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane
• THE ALIGNED K-CENTER PROBLEM
• On the Complexity of Some Common Geometric Location Problems
• Generalized Selection and Ranking: Sorted Matrices
• An Efficient Algorithm for 2D Euclidean 2-Center with Outliers
• Optimal Algorithms for the Weighted p-Center Problems on the Real Line for Small p
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• New Results on the Complexity of p-Centre Problems
• Algorithms for finding P-centers on a weighted tree (for relatively small P)
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• Polynomially bounded algorithms for locatingp-centers on a tree
• Stochastic k-Center and j-Flat-Center Problems
• Slowing down sorting networks to obtain faster sorting algorithms
• Finding kth paths and p-centers by generating and searching good data structures
• The $p$-Center Problem in Tree Networks Revisited
• Covering uncertain points in a tree