Berapa pathwidth dari 3D-grid (mesh atau lattice) dengan sidelength k?

12

Saya menanyakan pertanyaan ini beberapa minggu yang lalu di mathoverflow , tetapi saya tidak mendapat jawaban.

Di sini, dengan 3D-grid sidelength maksud saya grafik G = ( V , E ) dengan V = { 1 , ... , k } 3 dan E = { ( ( a , b , c ) , ( x , y , z ) ) | a - x | + | b - y | + | ckG=(V,E)V={1,,k}3 , yaitu, node ditempatkan pada koordinat integer 3 dimensi antara 1 dan k , dan sebuah node terhubung ke paling banyak 6 node lain yang berbeda dalam satu koordinat dengan satu.E={((a,b,c),(x,y,z))|ax|+|by|+|cz|=1}k

Apa nama grafik ini? Saya akan menggunakan kisi 3D, tetapi mungkin kisi 3D atau kisi 3D adalah yang biasa digunakan orang lain.

Berapa treewidth atau pathwidth dari grafik ini? Apakah ini sudah diterbitkan di suatu tempat?

Aku sudah tahu bahwa , yaitu itu benar-benar lebih kecil dari k 2 . Bagi saya, ini menunjukkan bahwa argumen standar menunjukkan bahwa k × k 2D-grid memiliki treewidth dan pathwidth k tidak akan mudah digeneralisasi.tw(G)=(3/4)k2+O(k)k2k×kk

Untuk melihat ini, kami mempertimbangkan dekomposisi jalur yang "menyapu" grid menggunakan set simpul terutama dari bentuk . Amati | S c | ( 3 / 4 ) k 2 + O ( k ) , S 3 / 2 k menjadi set tersebut terbesar. Set antara S c danSc={(x,y,z)x+y+z=c}|Sc|(3/4)k2+O(k)S3/2kSc dibuat dengan menyapu dengan garis dan membutuhkan O ( k ) simpul tambahan untuk menjadi pemisah. Lebih tepatnya, gunakan set S c , d = { ( x , y , z ) ( x + y + z = c x d ) ( x + y + z = c x d ) }Sc+1O(k)Sc,d={(x,y,z)(x+y+z=cxd)(x+y+z=cxd)}sebagai dekomposisi jalur .G

Saya juga punya ide untuk bukti yang menunjukkan , tetapi itu belum selesai.tw(G)=Ω(k2)

Riko Jacob
sumber
untuk c = k / 2 . Apakah saya melewatkan sesuatu? |Sc|=Ω(k2)c=k/2
Sariel Har-Peled
Tentu. Tapi hanya digunakan di batas atas. Yang benar-benar saya pedulikan adalah batas bawah. Sc
Riko Jacob
Anda mungkin tertarik dengan makalah ini: springerlink.com/content/3nmjlc1g5emx9vpk . Jika Anda dapat menghitung "nomor antrian" dari grafik Anda, maka Anda akan diberi batas bawah pada nya jalan-lebar menggunakan Teorema 1 yang menyatakan bahwa untuk grafik setiap G . qn(G)pw(G)G
Mathieu Chapelle
Oh Saya melihat. Anda berarti . (3/4)k2
Sariel Har-Peled
1
@ Sariel: Saya mengedit pertanyaan untuk menghindari kebingungan yang sama.
Tsuyoshi Ito

Jawaban:

13

The pathwidth dari dapat ditentukan sebagai konsekuensi untuk beberapa hasil dikenal. FitzGerald [2] menunjukkan bahwa bandwidth P 3 k adalah 3Pk3Pk3. Harper [3] menunjukkan suatu kondisi sedemikian rupa sehingga jika sebuah grafik memenuhi kondisi tersebut, maka jalurnya dan bandwidthnya sama. Moghadam [4,5] dan Bollobás and Leader [1] secara independen menunjukkan bahwa setiap grid multi-dimensi memenuhi kondisi Harper. Hasil ini menyiratkan bahwa lebar jalurP 3 k juga334k2+12kPk3.34k2+12k

Dalam makalah kami yang disebutkan oleh Hsien-Chih, kami menggeneralisasi hasil FitzGerald seperti yang dijelaskan Yoshio. Saya percaya treewidth dari tidak diketahui.Pk3

FYI: Saya baru saja mengirimkan versi bahasa Inggris dari makalah kami ke arXiv.

  1. B. Bollobás dan I. Pemimpin, Kompresi dan ketidaksetaraan isoperimetrik, J. Combin. Teori Ser. A 56 (1991) 47-62.
  2. CH FitzGerald, Pengindeksan optimal dari simpul grafik, Matematika. Comp. 28 (1974), 825-831.
  3. LH Harper, penomoran yang optimal dan masalah isoperimetri pada grafik, J. Combin. Teori 1 (1966) 385-393.
  4. HS Moghadam, operator Kompresi dan solusi untuk masalah bandwidth dari produk paths, Ph.D. tesis, Universitas California, Riverside (1983).n
  5. HS Moghadam, Bandwidth dari produk paths, Congr. Angka 173 (2005) 3-15.n
Yota Otachi
sumber
Terima kasih telah berbaik hati membagikan hasil baru Anda (dan kertas!) Juga, selamat datang di TCS SE :)
Hsien-Chih Chang 張顯 之
@ Hsien-Chih: Anda membuat saya memutuskan untuk membagikan hasil kami :-) Terima kasih. Bahkan, saya juga baru untuk arXiv.
Yota Otachi
6

Pathwidth dari 3D-grid telah dipelajari oleh Ryohei Suda, Yota Otachi dan Koichi Yamazaki dalam paper Pathwidth dari grid 3-dimensi , IEICE Tech. Laporan, 2009.

Diklaim dalam abstrak makalah itu

Dalam makalah ini, kami memberikan pathwidth dari grid 3-dimensi dalam bentuk tertutup, dengan menentukan lebar batas verteks mereka.

Namun batas yang tepat tidak dinyatakan dalam abstrak, dan saat ini saya tidak dapat mengakses kertas lengkap. Mungkin Anda dapat menghubungi penulis secara pribadi, dan memposting jawaban untuk pertanyaan ini sendiri, jika penulis bersedia membagikan hasilnya.

Hsien-Chih Chang 張顯 之
sumber
Perhatikan bahwa makalah ini ditulis dalam bahasa Jepang.
Tsuyoshi Ito
@ Tsuyoshi: Ya, kami mungkin membutuhkan bantuan Anda :)
Hsien-Chih Chang 張顯 之
4
P×Pm×Pnm+mn+2m(+mn12)2Pkkmn
pw(Pk3)=34k2+O(k)
Terima kasih. Sepertinya saya tidak perlu merasa sedih karena tidak menemukan referensi itu sendiri. Saya ingin tahu detailnya.
Riko Jacob