2-medians in trees with pos/neg weights (Q1582068)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | 2-medians in trees with pos/neg weights |
scientific article |
Statements
2-medians in trees with pos/neg weights (English)
0 references
27 February 2001
0 references
Consider the positive/negative 2-median problem on a tree of \(n\) vertices. The authors give an \(O(n^2)\) algorithm to solve the problem when the objective function is given as the sum of the minima of the weighted distances between vertices of the tree and facilities, and an \(O(n^3)\) algorithm to solve the problem when the objective function is given as the sum of the weighted minima of the distances between vertices of the tree and facilities.
0 references
location problem
0 references
median problem
0 references
obnoxious facilities
0 references
