74366

Автор(ы): 

Автор(ов): 

1

Параметры публикации

Тип публикации: 

Тезисы доклада

Название: 

Vertex stability radius in the shortest path problem

Электронная публикация: 

Да

Наименование конференции: 

  • 13th International Conference on Network Analysis (NET 2023, Nizhny Novgorod)

Наименование источника: 

  • Abstract Book of the 13th International Conference on Network Analysis (Nizhny Novgorod, Russia, 2023)

Город: 

  • Нижний Новгород

Издательство: 

  • National Research University Higher School of Economics

Год издания: 

2023

Страницы: 

18-19
Аннотация
We study the shortest path problem in graphs with perturbed edge weights. The stability radius is a concept that measures how much a solution to the shortest path problem can change when the input data is perturbed. Common definition of the stability radius can be expressed as the maximum amount of perturbation that can be applied to the edge weights without changing the optimal solution (or the lack of new optimal solutions). We introduce new concepts of vertex stability radius, which measure how much the edge weights can be changed without affecting the existence of an optimal path passing through a given vertex. Thus, we do not consider individual solutions or sets of solutions, but some characteristic of them. This characteristic is that the given vertex belongs to the set of optimal paths before and after perturbations of edge weights. Practical applications of the introduced concepts of the stability radius are also given.

Библиографическая ссылка: 

Гришин Е.М. Vertex stability radius in the shortest path problem / Abstract Book of the 13th International Conference on Network Analysis (Nizhny Novgorod, Russia, 2023). Н. Новгород: National Research University Higher School of Economics, 2023. С. 18-19.