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

DOI10.1007/S00186-006-0121-1zbMATH Open1156.90450OpenAlexW2059431632MaRDI QIDQ1006548FDOQ1006548

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

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

zbMATH Keywords

location theory\(p\)-median problemobnoxious facilities

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Computing the 2‐median on tree networks in O(n lg n) time
• Title not available (Why is that?)
• Discrete location problems with push-pull objectives
• The \(p\)-maxian problem on a tree
• Obnoxious Facility Location on Graphs
• Improved complexity bounds for location problems on the real line
• 2-medians in trees with pos/neg weights

Cited In (13)

• The backup 2-median problem on block graphs
• The \(p\)-maxian problem on block graphs
• An ant colony algorithm for the pos/neg weighted \(p\)-median problem
• Inverse quickest center location problem on a tree
• 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)