Di Graphic TSP , Anda diberi grafik tidak diarahkan dan tujuannya adalah untuk menemukan tur terpendek di G yang mengunjungi setiap titik setidaknya satu kali . Catatan bahwa ini adalah tidak sama dengan menemukan sirkuit Hamilton di G . Pertanyaan saya adalah:
Apa kompleksitas TSP Grafis pada grafik treewidth terbatas?
Apakah ada kasus khusus Grafis TSP dengan algoritma waktu polinomial non-sepele?
sumber