Аннотация:
Исследуется плотность графа конусного разбиения, ассоциированного с задачей о кратчайшем пути. Устанавливается экспоненциальность плотности при отсутствии ограничения на длины дуг, а в случае классического варианта задачи для неотрицательных длин дуг показывается, что плотность полиномиальна. Библ. 6.
Ключевые слова:теория графов, плотность графа, ориентированный граф.
Полный текст:
PDF файл (675 kB)