Median problems with positive and negative weights on cycles and cacti

DOI10.1007/s10878-008-9187-4zbMath1198.90263OpenAlexW2030187521MaRDI QIDQ604872

Rainer E. Burkard, Johannes Hatzl

Publication date: 12 November 2010

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

Full work available at URL: https://doi.org/10.1007/s10878-008-9187-4

zbMATH Keywords

location problemsobnoxious facilitiesmedian problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Discrete location and assignment (90B80)

Related Items

The connected \(p\)-median problem on block graphs, Two Paths Location of a Tree with Positive or Negative Weights, The backup 2-median problem on block graphs, Two paths location of a tree with positive or negative weights, A modified optimal algorithm for 2-maxian location problems on cactus graphs, Median problems on wheels and cactus graphs, Inverse quickest center location problem on a tree, The 2-maxian problem on cactus graphs

Cites Work

• Unnamed Item
• A polynomial method for the pos/neg weighted 3-median problem on a tree
• A linear algorithm for the pos/neg-weighted 1-median problem on a cactus
• 2-medians in trees with pos/neg weights
• The \(p\)-maxian problem on a tree
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Computing the 2‐median on tree networks in O(n lg n) time
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
• Efficient computation of 2-medians in a tree network with positive/negative weights