|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Многогранники коммивояжера и разрезов. Аффинная сводимость
А. Н. Максименко
Аннотация:
Пусть $STSP_m$ – многогранник задачи коммивояжера для $m$ городов, а $CUT_n$ – многогранник разрезов полного графа на $n$ вершинах. Показано, что $CUT_n$ аффинно эквивалентен одной из граней многогранника $STSP_m$ при $m=(2n-2)(2n-3)$. С другой стороны, $STSP_m$ является аффинным образом одной из граней многогранника $CUT_n$ при $n=(m-1)^2+1$.
Статья поступила: 09.09.2009
Образец цитирования:
А. Н. Максименко, “Многогранники коммивояжера и разрезов. Аффинная сводимость”, Дискрет. матем., 25:2 (2013), 31–38; Discrete Math. Appl., 23:3-4 (2013), 251–259
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1232https://doi.org/10.4213/dm1232 https://www.mathnet.ru/rus/dm/v25/i2/p31
|
Статистика просмотров: |
Страница аннотации: | 392 | PDF полного текста: | 233 | Список литературы: | 66 | Первая страница: | 40 |
|