Weighted Admissible Absolute 1-Center Problem

S.I. Fainshtein1), A.S. Fainshtein1), V.E. Torchinsky1)

1) Nosov Magnitogorsk State Technical University, Magnitogorsk, Russia
Аннотация

This paper presents a polynomial algorithm for new generalization of the absolute 1-center problem (A1CP) in general undirected graph with each edge having a positive weight vector (length for the first coordinate and costs for all the other coordinates) and with each vertex having non-negative weight vector. We assume that the cost is a linear function of the length on edge. Non-negative cost boundaries are also given. AA1CP (admissible absolute 1-center problem) minimizes the weighted length of path between a point on edge and the farthest vertex provided that any weighted cost of path from the point to any vertex does not exceed the corresponding cost boundary.

Ключевые слова

vertex-weighted absolute 1-center problem, admissible absolute 1-center problem