Pertanyaan yang diberi tag treewidth

13
Apa definisi yang benar dari

Seperti judulnya, apa definisi yang benar dari -tree? Ada beberapa kertas yang berbicara tentang k -trees dan parsial k -trees sebagai definisi alternatif untuk grafik dengan treewidth dibatasi, dan saya telah melihat banyak definisi yang tampaknya tidak benar. Misalnya, setidaknya satu tempat...

12
Apakah treewidth

Biarkan kkk diperbaiki, dan biarkan GGG menjadi grafik (terhubung). Jika saya tidak salah, itu berasal dari karya Bodlaender [1, Teorema 3.11] bahwa jika treewidth GGG kira-kira setidaknya 2k32k32k^3 , maka GGG berisi bintang K1,kK1,kK_{1,k} sebagai minor. Bisakah kita membuat istilah 2k32k32k^3...

10
Hubungan antara lebar pohon dan jumlah klik

Apakah ada kelas grafik yang bagus yang lebar pohon dibatasi oleh fungsi dari angka klik , yaitu ?t w ( G )tw(G)tw(G)ω ( G )ω(G)\omega(G)t w ( G ) ≤ f( ω ( G ) )tw(G)≤f(ω(G))tw(G)\leq f(\omega(G)) Sebagai contoh, ini adalah fakta klasik bahwa untuk setiap grafik chordal , kita memiliki . Jadi,...

10
Kelas grafik dengan treewidth superconstant

Ada beberapa kelas grafik yang menarik dengan treewidth terikat. Misalnya, pohon (treewidth 1), seri grafik paralel (treewidth 2), grafik outerplanar (treewidth 2), grafik kkk -outerplanar (treewidth O (k)), grafik lebar cabang (treewidth O (k)), .. .kkk Pertanyaan: Apakah ada contoh kelas grafik...

9
Kasus khusus Grafis TSP

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:GGGGGGGGG Apa kompleksitas TSP...