A polynomial method for the pos/neg weighted 3-median problem on a tree

DOI10.1007/S00186-006-0121-1MaRDI QIDQ1006548zbMATH OpenOpenAlexFDO

Authors Rainer E. Burkard, Jafar Fathali

Publication date 25 March 2009

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00186-006-0121-1

zbMATH Keywords

location theory\(p\)-median problemobnoxious facilities

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Continuous location (90B85)

Recommendations

• Polyhedral properties of the \(K\)-median problem on a tree
• A polynomial algorithm for the two-connections variant of the tree \(p\)-median problem
• Some polynomially solvable cases of the inverse ordered 1-median problem on trees
• 2-medians in trees with pos/neg weights
• An O(pn^ 2) algorithm for the p-median and related problems on tree graphs
• scientific article; zbMATH DE number 4085448
• Efficient computation of 2-medians in a tree network with positive/negative weights
• Efficient computation of 2-medians in a tree network with positive/negative weights
• An inverse approach to convex ordered median problems in trees
• A linear algorithm for the pos/neg-weighted 1-median problem on a cactus

Cites work

• scientific article; zbMATH DE number 44281 (Why is no real title available?)
• scientific article; zbMATH DE number 1340521 (Why is no real title available?)
• scientific article; zbMATH DE number 1091317 (Why is no real title available?)
• scientific article; zbMATH DE number 1746287 (Why is no real title available?)
• scientific article; zbMATH DE number 3328106 (Why is no real title available?)
• 2-medians in trees with pos/neg weights
• A linear algorithm for the pos/neg-weighted 1-median problem on a cactus
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• An O(pn^ 2) algorithm for the p-median and related problems on tree graphs
• Computing the 2‐median on tree networks in O(n lg n) time
• Discrete location problems with push-pull objectives
• Improved complexity bounds for location problems on the real line
• Obnoxious Facility Location on Graphs
• The p-maxian problem on a tree

Cited in

(13)

• The backup 2-median problem on block graphs
• The \(p\)-maxian problem on block graphs
• Inverse quickest center location problem on a tree
• An ant colony algorithm for the pos/neg weighted \(p\)-median problem
• A quadratic time exact algorithm for continuous connected 2-facility location problem in trees
• The connected p-median problem on block graphs
• Median problems with positive and negative weights on cycles and cacti
• The pos/neg-weighted median problem on block graphs with subgraph-shaped customers
• A hybrid artificial bee colony algorithm for the p-median problem with positive/negative weights
• Finding a core of a tree with pos/neg weight
• A genetic algorithm for the p-median problem with pos/neg weights
• The pos/neg-weighted 1-median problem on tree graphs with subtree-shaped customers
• The pos/neg-weighted 2-medians in balanced trees with subtree-shaped customers

This page was built for publication: A polynomial method for the pos/neg weighted 3-median problem on a tree

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