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

DOI10.4230/LIPICS.SOCG.2018.72zbMATH Open1489.68210OpenAlexW2962711322MaRDI QIDQ5116532FDOQ5116532

Publication date: 18 August 2020

Full work available at URL: https://doi.org/10.4230/LIPIcs.SoCG.2018.72

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

Cites Work

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

Cited In (7)

Distance Domination in Graphs
A linear algorithm for finding the k‐broadcast center of a tree
Finding broadcast 2-centers of a tree under the postal model
Covering uncertain points in a tree
Title not available (Why is that?)
A linear-time algorithm for radius-optimally augmenting paths in a metric space
The weighted $k$-center problem in trees for fixed $k$

This page was built for publication: An O(n log n)-Time Algorithm for the k-Center Problem in Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116532)