The weighted k-center problem in trees for fixed k

DOI10.1016/J.TCS.2022.01.005OpenAlexW4206493951MaRDI QIDQ2077394FDOQ2077394

Binay Bhattacharya, Sandip Das, S. Dev

Publication date: 21 February 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.01.005

zbMATH Keywords

facility location problem\(k\)-center problemparametric prune and search

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
• A Best Possible Heuristic for the k-Center Problem
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• Asymmetric k -center is log ^* n -hard to approximate
• AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem
• A simple heuristic for the p-centre problem
• A heuristic for the p-center problem in graphs
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Easy and hard bottleneck location problems
• An \(O(n \log^2 n)\) algorithm for the optimal sink location problem in dynamic tree networks
• New Results on the Complexity of p-Centre Problems
• Algorithms for finding P-centers on a weighted tree (for relatively small P)
• Improved algorithms to network \(p\)-center location problems
• Efficient algorithms for center problems in cactus networks
• Some variations on constrained minimum enclosing circle problem
• An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees
• Optimal Algorithms for the Weighted p-Center Problems on the Real Line for Small p
• Linear-time fitting of a \(k\)-step function
• The $p$-Center Problem in Tree Networks Revisited
• A 2-approximation algorithm and beyond for the minimum diameter \(k\)-Steiner forest problem
• Approximating the asymmetric \(p\)-center problem in parameterized complete digraphs
• Asymmetry in \(k\)-center variants
• An O(n log n)-Time Algorithm for the k-Center Problem in Trees

Cited In (5)

• Title not available (Why is that?)
• Center problems with pos/neg weights on trees
• w-Centroids and Least (w, l)-Central Subtrees in Weighted Trees
• \((r,p)\)-centroid problems on paths and trees
• A note on the robust 1-center problem on trees

This page was built for publication: The weighted \(k\)-center problem in trees for fixed \(k\)

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