An O(n n)-time algorithm for the k-center problem in trees

DOI10.4230/LIPICS.SOCG.2018.72MaRDI QIDQ5116532zbMATH OpenOpenAlexFDO

Authors Haitao Wang, Jingru Zhang

Publication date 18 August 2020

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

zbMATH Keywords

\(k\)-centerfacility locationstrees

Mathematics Subject Classification ID

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

Recommendations

• An O(n n)-time algorithm for the k-center problem in trees
• The p-center problem in tree networks revisited
• Algorithms for finding P-centers on a weighted tree (for relatively small P)
• An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees
• Efficient algorithms for the one-dimensional \(k\)-center problem

Cites work

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

Cited in

(14)

• The weighted \(k\)-center problem in trees for fixed \(k\)
• Distance domination in graphs
• An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees
• scientific article; zbMATH DE number 177557 (Why is no real title available?)
• scientific article; zbMATH DE number 1091558 (Why is no real title available?)
• Efficient algorithms for the one-dimensional \(k\)-center problem
• A linear algorithm for finding the k‐broadcast center of a tree
• The p-center problem in tree networks revisited
• Mathematical Foundations of Computer Science 2003
• An O(n n)-time algorithm for the k-center problem in trees
• The weighted k-center problem in trees for fixed k
• A linear-time algorithm for radius-optimally augmenting paths in a metric space
• Finding broadcast 2-centers of a tree under the postal model
• A subquadratic time algorithm for the weighted k-center problem on cactus graphs

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)