A linear time algorithm for the p-maxian problem on trees with distance constraint

DOI10.1007/S10878-020-00650-9MaRDI QIDQ830937zbMATH OpenOpenAlexFDO

Authors Nguyen Thanh Hung, Huong Nguyen-Thu, Trung-Kien Nguyen

Publication date 10 May 2021

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-020-00650-9

zbMATH Keywords

convexlocation problemmaxian problemtree

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Discrete location and assignment (90B80) Combinatorial optimization (90C27)

Recommendations

• Distance-constrained multifacility minimax location problems on tree networks
• Facility location on a tree with maximum distance constraints
• The balanced 2-median and 2-maxian problems on a tree
• Inverse center location problem on a tree
• The inverse \(p\)-maxian problem on trees with variable edge lengths

Cites work

• A linear time algorithm for computing minmax regret 1-median on a tree network
• A review of extensive facility location in networks
• Algorithmic results for ordered median problems
• Algorithms for connected \(p\)-centdian problem on block graphs
• An O(pn^ 2) algorithm for the p-median and related problems on tree graphs
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees
• Computing the 2‐median on tree networks in O(n lg n) time
• Discrete location problems with push-pull objectives
• Extensive facility location problems on networks: an updated review
• scientific article; zbMATH DE number 1746287 (Why is no real title available?)
• Inverse 1-median problem on block graphs with variable vertex weights
• Inverse median problems
• Location theory. A unified approach
• Minmax Regret Median Location on a Network Under Uncertainty
• Obnoxious Facility Location on Graphs
• The 2-maxian problem on cactus graphs
• The p-maxian problem on a tree
• The \(p\)-maxian problem on block graphs
• The \(p\)-Maxian problem on interval graphs
• The connected p-center problem on block graphs with forbidden vertices
• The connected \(p\)-center problem on cactus graphs
• The connected p-median problem on block graphs
• The inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance

Cited in

(5)

• The p-maxian problem on a tree
• The balanced 2-median and 2-maxian problems on a tree
• On a quadratic programming problem involving distances in trees
• A strongly polynomial time algorithm for the maximum supply rate problem on trees
• A strongly polynomial time algorithm for the maximum supply rate problem on trees

This page was built for publication: A linear time algorithm for the \(p\)-maxian problem on trees with distance constraint

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