2-medians in trees with pos/neg weights

DOI10.1016/S0166-218X(00)00177-3zbMath0986.90017OpenAlexW2029412688MaRDI QIDQ1582068

Rainer E. Burkard, Helidon Dollani, Eranda Çela

Publication date: 27 February 2001

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00177-3

zbMATH Keywords

location problemobnoxious facilitiesmedian problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Discrete location and assignment (90B80)

Related Items (24)

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees ⋮ A genetic algorithm for the \(p\)-median problem with pos/neg weights ⋮ Median problems with positive and negative weights on cycles and cacti ⋮ Two Paths Location of a Tree with Positive or Negative Weights ⋮ The multi-facility median problem with Pos/Neg weights on general graphs ⋮ A hybrid artificial bee colony algorithm for the \(p\)-median problem with positive/negative weights ⋮ The backup 2-median problem on block graphs ⋮ Finding a core of a tree with pos/neg weight ⋮ Two paths location of a tree with positive or negative weights ⋮ The balanced 2-median and 2-maxian problems on a tree ⋮ A branch-and-cut method for the obnoxious \(p\)-median problem ⋮ An ant colony algorithm for the pos/neg weighted \(p\)-median problem ⋮ The \(p\)-maxian problem on a tree ⋮ The pos/neg-weighted 2-medians in balanced trees with subtree-shaped customers ⋮ Discrete location problems with push-pull objectives ⋮ The pos/neg-weighted 1-median problem on tree graphs with subtree-shaped customers ⋮ The \(p\)-maxian problem on block graphs ⋮ The pos/neg-weighted median problem on block graphs with subgraph-shaped customers ⋮ Efficient computation of 2-medians in a tree network with positive/negative weights ⋮ Efficient algorithms for two generalized 2-median problems and the group median problem on trees ⋮ A polynomial method for the pos/neg weighted 3-median problem on a tree ⋮ Efficient computation of 2-medians in a tree network with positive/negative weights ⋮ Solving the \(p\)-median problem with pos/neg weights by variable neighborhood search and some results for special cases ⋮ The 2-maxian problem on cactus graphs

Cites Work

• Unnamed Item
• Dynamic and static algorithms for optimal placement of resources in a tree
• Improved complexity bounds for location problems on the real line
• A linear algorithm for the pos/neg-weighted 1-median problem on a cactus
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• On the Complexity of Some Common Geometric Location Problems
• Off-Line Maintenance of Planar Configurations
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Worst-Case and Probabilistic Analysis of a Geometric Location Problem
• Obnoxious Facility Location on Graphs
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms

This page was built for publication: 2-medians in trees with pos/neg weights