Aplikasi Vertex Cover di dunia nyata

22

Aplikasi apa yang dimiliki Masalah Penutup Vertex di dunia nyata?

Industri atau proyek penelitian mana yang menggunakan perangkat lunak yang benar-benar diimplementasikan yang didasarkan pada hasil teoritis untuk masalah Vertex Cover? Secara khusus, apakah ada hasil teoretis berikut yang diterapkan dalam perangkat lunak yang digunakan?

  • Algoritma pendekatan untuk Penutup Vertex
  • Algoritma eksponensial-waktu untuk Vertex Cover
  • Algoritma traktable parameter-tetap untuk Penutup Vertex
  • Algoritma kernelisasi untuk Vertex Cover
ds.algorithms graph-theory graph-algorithms scatman
sumber
6
salah satu contoh yang baik adalah di wiki pada kondisi balapan: en.wikipedia.org/wiki/Vertex_cover#Contoh Juga sebagai motivasi orang memberikan contoh pemantauan. Di setiap titik solusi, kami menyimpan monitor. Saya pribadi berpikir bahwa googling jawaban ini adalah pilihan yang lebih baik daripada menanyakannya di sini.
singhsumit
5
Menurut Anda mengapa vertex cover memiliki aplikasi dunia nyata?
Jukka Suomela
3
Saya kira jawabannya adalah bahwa penutup simpul tidak memiliki aplikasi yang signifikan. Tetapi orang-orang mempelajarinya karena penutup simpul adalah kasus khusus sederhana dari masalah penutup yang ditetapkan. Setel penutup memang memiliki aplikasi. Dan Anda tidak dapat benar-benar memahami kompleksitas komputasi dari masalah penutup depan jika Anda tidak terlebih dahulu memahami kasus khusus sederhana (dan tidak terlalu sederhana) seperti penutup sudut, penutup tepi, set dominasi, dll.
Jukka Suomela
3
Seperti dicatat di en.wikipedia.org/wiki/Vertex_cover#Properti verteks tidak dalam bentuk penutup vertex terkecil membentuk satu set independen terbesar, jadi ini pada dasarnya masalah yang sama. Ada banyak aplikasi dunia nyata dari masalah himpunan independen, misalnya karena setiap masalah kepuasan kendala dapat dikurangi secara langsung.
András Salamon
5
@ András: Ini adalah poin yang bagus, tetapi korespondensi hanya berlaku untuk penutup simpul terkecil dan set independen terbesar. Dari perspektif algoritma yang tepat, ini pada dasarnya adalah masalah yang sama, tetapi jika kita tertarik pada algoritma yang efisien, kita biasanya puas dengan beberapa jenis perkiraan. Dan kemudian ternyata masalah penutup simpul memiliki sifat unik yang tidak dibagi dengan masalah set independen. Contoh favorit saya berasal dari komputasi terdistribusi: selimut vertex kecil tidak memerlukan pemecahan simetri, set independen besar memerlukannya.
Jukka Suomela

Jawaban:

13

Beberapa masalah di bidang biologi komputasi tampaknya cocok untuk aplikasi praktis yang tidak artifisial - atau setidaknya tidak artifisial seperti masalah yang disebutkan oleh Jukka Suomela.

Misalnya, orang sering menyebut karya oleh F. Abu-Khzam, R. Collins, M. Fellows, M. Langston, W. Suters C. Symons, Algoritma Kernelisasi untuk Vertex Cover Problem: Teori dan Eksperimen , Prosiding ke-6 Workshop Teknik Algoritma dan Eksperimen (ALENEX), ACM / SIAM, Proc. Matematika Terapan 115, 2004.

Seperti yang dinyatakan oleh penulis, "Salah satu aplikasi yang telah kami terapkan metode kami melibatkan menemukan pohon filogenetik berdasarkan informasi domain protein, ..." (bagian 8 dari makalah di atas).

Sekelompok penulis memiliki makalah yang serupa tentang topik ini, lihat, misalnya, Faisal N. Abu-Khzam, Michael A. Langston, Pushkar Shanbhag dan Christopher T. Symons, Algoritma Paralel yang Dapat Ditingkatkan untuk Masalah FPT , Algorithmica, Volume 45, Nomor 3 , 269-284.

Saya tidak yakin apakah contoh yang digunakan dalam eksperimen itu adalah dunia nyata atau buatan, tapi saya harap dua referensi memberi Anda titik awal yang baik.

Alexander Langer
sumber
4
"Setidaknya tidak semanis masalah yang disebutkan oleh Jukka Suomela" - dan aku berusaha berhati-hati untuk tidak menyebutkan masalah apa pun di sini!
Jukka Suomela
9

Contohnya mungkin bahwa tepi grafik mewakili jalan sedangkan simpul mewakili persimpangan. Tugasnya adalah menempatkan kamera keamanan di persimpangan jalan dengan cara yang akan membuat Anda melihat seluruh kota tetapi lebih baik menggunakan kamera sesedikit mungkin untuk menghemat uang.

galbarm
sumber
21
Masalah dengan contoh-contoh seperti ini adalah bahwa mereka cenderung menjadi contoh mainan. Mereka dapat digunakan untuk mengilustrasikan definisi tersebut, tetapi saya rasa tidak mungkin untuk menemukan referensi ke contoh dunia nyata di mana orang-orang telah benar-benar memilih lokasi kamera keamanan dengan menemukan penutup vertex minimum. Masalah dunia nyata seperti ini cenderung memiliki kendala tambahan, banyak di antaranya bahkan tidak terdefinisi dengan baik, dan solusinya cenderung serakah dan bertahap (instal dulu beberapa kamera keamanan di lokasi paling kritis, dan kemudian pasang lagi) ketika kami mendapat lebih banyak dana).
Jukka Suomela
Saya akan mendorong sedikit keberatan Jukka. Penting untuk menyaring masalah ke bagian inti yang menantang secara komputasi atau konseptual. Terlepas dari semua kendala dunia nyata tambahan, saya berpikir bahwa kesulitan komputasi inti dalam memilih kamera untuk menutupi ruang di dunia nyata, pada dasarnya, merupakan masalah penutup sudut. Tentu saja dalam hal ini algoritma aproksimasi baik-baik saja; tidak perlu menemukan penutup vertex terbaik. Dan dalam hal ini grafiknya akan cukup sederhana, mungkin planar misalnya.
6005
8

Anda juga dapat melihat di http://www.dharwadker.org/pirzada/applications/ . Ini tentang aplikasi Teori Grafik. Ini menyatakan beberapa aplikasi untuk vertex cover juga, seperti dalam biokimia dan menyelesaikan masalah perakitan SNP atau dalam masalah keamanan jaringan komputer.

Saeedn
sumber
1

Bagi saya itu agak mengejutkan bahwa penutup simpul minimum adalah subproblem dari Algoritma Hongaria , yaitu ketika menentukan satu set minimal garis horizontal atau vertikal yang mencakup semua nol yang dihasilkan dengan mengurangkan minima baris dan kolom.

Itu sama dengan menemukan penutup vertex minimal dalam grafik bipartit yang, juga mengejutkan, dapat diselesaikan dalam waktu polinomial yang dijelaskan dengan baik di sini

Manfred Weis
sumber