В графическом TSP вы получаете невзвешенный неориентированный графи цель состоит в том, чтобы найти кратчайший тур в который посещает каждую вершину хотя бы один раз . Обратите внимание , что это не так же , как найти гамильтонов цикл в . Мои вопросы:
Какова сложность Graphic TSP на ограниченных трехуровневых графах?
Существуют ли какие-либо особые случаи графического TSP с нетривиальными алгоритмами за полиномиальное время?
источник