Евклидова задача коммивояжера: различия между версиями

Подход динамического программирования, используемый Аророй [1] и Митчеллом [13], также имеет отношение к недавним достижениям в области нескольких проблем оптимизации для планарных графов. В частности, Арора и коллеги [3] разработали PTAS для задачи коммивояжера на взвешенных планарных графах; существует также PTAS для задачи нахождения двусвязного остовного подграфа планарного графа, имеющего минимальную стоимость [6].