RUS  ENG
Полная версия
ЖУРНАЛЫ // Журнал вычислительной математики и математической физики // Архив

Ж. вычисл. матем. и матем. физ., 2004, том 44, номер 9, страницы 1693–1696 (Mi zvmmf784)

Эта публикация цитируется в 5 статьях

Комбинаторные свойства многогранника задачи о кратчайшем пути

А. Н. Максименко

150008 Ярославль, ул. Союзная, 144, Ярославский гос. ун-т, каф. Дискретного анализа

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

Ключевые слова: теория графов, плотность графа, ориентированный граф.

УДК: 519.712.63

MSC: Primary 90C57; Secondary 05C85, 68Q25, 90C35

Поступила в редакцию: 10.02.2002


 Англоязычная версия: Computational Mathematics and Mathematical Physics, 2004, 44:9, 1611–1614

Реферативные базы данных:


© МИАН, 2024