Partisi grafik sambil meminimalkan tepi antar-partisi

Saya sedang bekerja untuk mencoba mempartisi grafik triangulasi menjadi subgraph yang terhubung dengan beberapa jaminan pada jumlah tepi antar-partisi. Berikut adalah contoh grafik triangulasi yang telah dipartisi menjadi 4 "cluster":

Apa yang saya inginkan pada awalnya adalah algoritma yang dapat membuat partisi kira-kira segitiga k (mungkin ada beberapa kesalahan asalkan tidak terlalu besar), dan saya berhasil menemukan algoritma (di mana p adalah jumlah total partisi) yang bisa menemukan partisi seperti itu. Saya kemudian menyadari bahwa memiliki sejumlah besar tepi antar-partisi merugikan untuk aplikasi yang saya butuhkan untuk algoritma ini.$O(k^2p^2(v+e))$

Idealnya, saya ingin algoritma yang dapat menjaga setiap partisi dalam beberapa rentang , idealnya menjadikannya sebagai faktor konstan seperti 2. Juga, saya ingin dapat membuat jumlah antar-tepi memiliki batas atas itu "rendah".$k$

Selain itu, masalah lain yang saya miliki adalah jika saya memiliki partisi yang memiliki properti ini, dan saya memodifikasi grafik dengan melakukan salah satu dari yang berikut:

• Menambahkan satu set tepi yang terhubung ke simpul yang ada
• Menambahkan titik dan satu set tepi yang terhubung ke titik yang ditambahkan
• Menghapus satu set tepi
• Menghapus titik dan semua tepi yang terhubung ke titik ini

Saya ingin dapat mempartisi ulang grafik dan masih memiliki setiap partisi dengan ukuran dan jumlah cut edge diminimalkan. (Ini adalah solusi yang saya berikan untuk hadiah). Ini berarti bahwa dengan menggunakan algoritma ini, kita dapat membangun partisi apa pun dengan mulai dengan grafik kosong dan menambahkan simpul dan tepi satu per satu dan partisi ulang.$k$

Berikut adalah beberapa kendala tambahan untuk masalah ini:

• Grafiknya adalah planar
• Setiap "segitiga" adalah simpul yang memiliki tepi yang tidak terarah untuk membentuk segitiga dengan tepi yang sama
• Dari pernyataan di atas, jelas bahwa setiap simpul dalam grafik ini memiliki derajat paling banyak 3
• Grafik terhubung
• Setiap subgraph dari partisi terhubung
• Setiap subgraf memiliki kira-kira k simpul
• Paling banyak tepi antar-partisi (tepi yang berisi simpul dari partisi yang berbeda). Jika Anda dapat menemukan ikatan serupa untuk tepi antar-partisi seperti atau maka itu juga bisa berfungsi. Saya tidak sepenuhnya yakin batas atas untuk tepi antar-partisi bisa kurang dari jadi jika Anda dapat membuktikan bahwa tidak mungkin untuk melakukan yang lebih baik, itu memuaskan juga. 2$\sqrt n$ O(logn)O(n$2\sqrt n$$O(\log n)$$O(n)$

Saya pada titik di mana saya mandek, jadi bantuan apa pun dengan masalah ini akan menyenangkan. Jika Anda bisa mengatasi masalah ini, Anda adalah lutut para lebah. Kalau tidak, jika Anda mengetahui makalah atau buku pelajaran atau algoritma apa pun yang bisa Anda tunjukkan, saya akan sangat menghargainya.

Beri tahu saya jika saya perlu mengklarifikasi sesuatu!

EDIT: Berikut adalah beberapa kendala tambahan jika itu membuat masalah lebih mudah.

• Kami berhadapan dengan triangulasi delaunay terbatas
• Batasan tidak akan pernah menjadi satu titik
• Grafik yang dibuat dari triangulasi dibuat sebagai berikut: setiap segitiga direpresentasikan sebagai simpul. Setiap tepi dalam grafik sesuai dengan tepi yang tidak dibatasi dalam triangulasi. Ini berarti bahwa tepi terbatas antara dua segitiga tidak akan muncul dalam representasi grafik dari segitiga.

Hal lain yang saya sadari adalah bahwa kita mungkin perlu memodifikasi untuk tumbuh seiring bertambah, jika tidak maka tidak ada sub jaminan pada jumlah tepi antar-partisi.n O ( n $k$$n$$O(n)$

Rao memiliki dua makalah tentang pemotongan sparest dalam grafik planar, perkiraan faktor konstan dalam waktu kuasi-linear tampaknya mungkin . Pembelahan rekursif, meskipun tidak ideal, mungkin merupakan pendekatan yang layak untuk masalah Anda.

Satish Rao. Menemukan pemisah optimal dekat dalam grafik planar . Dalam Simposium ke 28 tentang Yayasan Ilmu Komputer (FOCS), halaman 225-237, 1987.

Satish Rao. Algoritma yang lebih cepat untuk menemukan potongan tepi kecil dalam grafik planar (abstrak yang diperluas). Dalam Simposium ACM ke-24 tentang Teori Komputasi (STOC), halaman 229-240, 1992.

Horst D. Simon dan Shang-Hua Teng. Seberapa Baik Pembelahan Rekursif? Dalam SIAM Journal on Scientific Computing, Volume 18, Edisi 5, halaman 1436-1445, 1997.

http://cse.iitkgp.ac.in/~pabitra/paper/barna-sdm07.pdf

$O(k^3)$$k = O(\log n)$

Algoritme berikut mungkin membantu.

1. Choose any vertex from the graph.

2. Do a BFS untill $O(K)$ vertices has been visited.

3. Create a cluster with the visited vertices. (Connectivity is ensured for the cluster).

4. Remover the visited vertices from the graph.

5. Repeat 1-4 untill all nodes are visited.

$O(K)$$O(K)$$O(N/K)$

Juga modifikasi grafik dengan menambahkan simpul tidak akan mempengaruhi partisi. Setiap satu partisi di mana salah satu tetangga dari vertex baru berada, yang dapat menjadi partisi dari vertex baru. Jadi, mungkin tidak diperlukan partisi ulang sampai ukuran salah satu cluster menjadi terlalu banyak.

Edit:

Berikut ini adalah bukti bahwa tidak mungkin untuk melakukan yang lebih baik daripada jumlah linier tepi antar-partisi untuk arbiter . Biarkan di beberapa partisi ada simpul m dan terhubung. Pada terbaik, yang sesuai segitiga akan membangun cembung daerah R . Sekarang untuk arbiter k lambung cembung dari R dapat mengandung O ( K $k$$m$$\mathscr{R}$$k$$\mathscr{R}$$O(K)$$O(K)$$\mathscr{R}$$k$$O(log n)$ maka mungkin saja tepi antar-partisi dapat dikurangi.

melakukan beberapa pencarian pada ini tetapi menunda postingan untuk melihat jawaban apa yang akan terwujud menjawab).

pada inspeksi ada banyak kendala yang diberikan pada masalah ini dan mungkin bisa mengambil seluruh kertas untuk membuat algoritma & membuktikan bahwa itu memenuhi semua itu (yang tentu saja umumnya di luar ruang lingkup format pertukaran stackex). Namun demikian, ada beberapa pendekatan dasar untuk mengatasi masalah ini

1. empiris. buat grafik acak yang sesuai dengan kendala atau gunakan grafik dari beberapa dataset yang cocok dengan kondisi dan coba algoritma yang berbeda padanya, dan lihat kinerjanya. orang mungkin menemukan bahwa suatu algoritma secara empiris memenuhi syarat reqd. jika seseorang lebih ketat, seseorang dapat mencoba untuk membuat bukti dari pengamatan empiris jika 100% puas dengan dataset besar. juga untuk penelitian empiris sering membantu untuk mengetahui bagaimana dataset diperoleh / dihasilkan, apa sifat / asal usulnya.

2. pertanyaan tidak memiliki kutipan terkait literatur / referensi. jadi apa jenis algoritma terdekat dalam literatur? untuk jenis masalah ini beberapa jenis area penelitian mungkin tumpang tindih. ada penelitian tentang grafik planar, partisi grafik, pemotongan grafik, pemisah grafik, partisi grafik segitiga, dll .; itu tidak jelas untuk mencari tahu tema utama dari pertanyaan ini sejauh dirumuskan atau sub-area penelitian tertentu (algoritma grafik) yang paling langsung menimpanya.

diberikan kualifikasi tersebut tema dasar dari pertanyaan tampaknya "mempartisi grafik planar". berikut adalah beberapa referensi terbaru tentang topik tersebut yang mungkin bermanfaat & menunjukkan tema / sudut tambahan dari penelitian terkait saat ini. ada beberapa algoritma yang diterapkan & mereka mungkin tersedia atas permintaan dari penulis.

3 ^rd melibatkan partisi dengan bobot, yang akan generalisasi ke bobot yang sama, tetapi yang memberikan kerangka kerja tambahan untuk dipertimbangkan / investigasi: bisa semua kondisi pertanyaan dipenuhi oleh beberapa jenis skema tugas berat badan? (Ini juga dapat dikaitkan dengan persyaratan untuk memiliki semacam kontrol dinamis atau penyesuaian atas solusi yang juga disebutkan dalam pertanyaan.)

• Karya partisi spektral: Grafik planar dan jerat elemen hingga Spielman / Teng

• Algoritma Linier untuk Masalah k-partisi Grafik Planar tanpa Menentukan Basis Wada, Chen

• Partisi grafik planar dengan biaya dan bobot Aleksandrov et al