МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
S.I. Fainshtein, A.S. Fainshtein, V.E. Torchinsky "Weighted Admissible Absolute 1-Center Problem"
МЕТОДЫ ОБРАБОТКИ ИЗОБРАЖЕНИЙ
СИСТЕМЫ УПРАВЛЕНИЯ
ПРИКЛАДНЫЕ АСПЕКТЫ ИНФОРМАТИКИ
S.I. Fainshtein, A.S. Fainshtein, V.E. Torchinsky "Weighted Admissible Absolute 1-Center Problem"
Abstract.
 
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. 

Keywords:
 
vertex-weighted absolute 1-center problem, admissible absolute 1-center problem. 
 
PP. 3-9. 

DOI 10.14357/20718632200201 
2020 / 02
2020 / 01
2019 / 04
2019 / 03

© ФИЦ ИУ РАН 2008-2018. Создание сайта "РосИнтернет технологии".