УДК 519.178

О неэффективности иерархической системы пересадок / Р. А. Савченко. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2015. № 5. С. 44-47.

Рассматривается задача поиска кратчайшего пути в графе с помощью системы пересадок. Доказывается, что иерархическая система пересадок может оказаться в \Omega(\sqrt n) раз больше минимальной (неиерархической) системы пересадок.

Ключевые слова: поиск кратчайшего пути в графе, система пересадок, иерархическая система пересадок.

Илл. 1. Библиогр. 6.