Pertama bertanya pada math.SE tanpa balasan.
- Misalkan saya memiliki grafik planar, dengan penanaman planar, bagaimana cara menemukan dekomposisi pohon?
- Apa dekomposisi pohon optimal dari -by- kotak persegi? Tidak sepenuhnya yakin bagaimana mendefinisikan "optimal", tetapi harus membedakan antara dekomposisi dengan satu tas besar dan dekomposisi dengan banyak tas besar.
ds.algorithms
graph-theory
graph-algorithms
treewidth
integer-lattice
Yaroslav Bulatov
sumber
sumber
Untuk pertanyaan pertama, terbuka apakah menemukan dekomposisi pohon untuk grafik planar dapat dilakukan dalam waktu polinomial. Algoritma aproksimasi terbaik mungkin adalah algoritma RatCatcher oleh Seymour dan Thomas, yang menghitung lebar cabang dari grafik planar, sehingga memiliki rasio aproksimasi 1,5 oleh hubungan antara lebar cabang dan treewidth.
Untuk yang kedua, kita memiliki teorema berikut tentang treewidth dari grids:k×k
Dan tas dapat diambil dengan ukuran , dengan total tas. Saya tidak yakin apakah ini yang Anda inginkan, jadi silakan melakukannya jika Anda memodifikasi definisi "optimal".k+1 k(k−1)
sumber
Jika Anda tidak ingin dekomposisi pohon optimal, Anda dapat membangun dekomposisi pohon dengan menghitung separator secara rekursif.
sumber