2-medians in trees with pos/neg weights (Q1582068): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 04:58, 5 March 2024
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
