|
Журнал вычислительной математики и математической физики, 2004, том 44, номер 9, страницы 1693–1696
(Mi zvmmf784)
|
|
|
|
Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)
Комбинаторные свойства многогранника задачи о кратчайшем пути
А. Н. Максименко 150008 Ярославль, ул. Союзная, 144, Ярославский гос. ун-т, каф. Дискретного анализа
Аннотация:
Исследуется плотность графа конусного разбиения, ассоциированного с задачей о кратчайшем пути. Устанавливается экспоненциальность плотности при отсутствии ограничения на длины дуг, а в случае классического варианта задачи для неотрицательных длин дуг показывается, что плотность полиномиальна. Библ. 6.
Ключевые слова:
теория графов, плотность графа, ориентированный граф.
Поступила в редакцию: 10.02.2002
Образец цитирования:
А. Н. Максименко, “Комбинаторные свойства многогранника задачи о кратчайшем пути”, Ж. вычисл. матем. и матем. физ., 44:9 (2004), 1693–1696; Comput. Math. Math. Phys., 44:9 (2004), 1611–1614
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/zvmmf784 https://www.mathnet.ru/rus/zvmmf/v44/i9/p1693
|
|