Diberikan grafik bipartit G=(U∪V,E)G=(U∪V,E)G = (U \cup V, E) dengan bobot positif, biarkan f:2U→Rf:2U→Rf: 2^U \rightarrow \mathbb{R} dengan f(S)f(S)f(S) sama dengan pencocokan berat maksimum dalam grafik G[S∪V]G[S∪V]G[S\cup V] . Benarkah fff adalah fungsi
Inilah masalah yang telah mengganggu saya untuk sementara waktu. Katakanlah string adalah urutan 1s dan 0s, dan string wildcard adalah urutan 1, 0, dan? S. Semua string dan string wildcard memiliki panjang yang sama. Ini adalah wildcard UNIX standar; 10 ?? 1 cocok 10011, 10111, dll - a? cocok...
Makalah SODA 2 halaman Kalai memberikan algoritma yang sederhana dan efisien untuk pencocokan pola dengan tidak peduli (wildcard yang cocok dengan satu karakter). Intinya, semudah berbelit-belit. Tetapi apa yang terjadi jika kita mencari beberapa pola dengan tidak peduli? Bisakah kita masih...
Diberikan grafik bipartit tanpa bobot . Apakah benar bahwa selalu ada pencocokan non -tyty M ⊆ E (belum tentu maksimal), sehingga untuk setiap ( i , j ) ∈ E dengan saya cocok dan j tidak cocok , ia memegang deg ( i ) > deg ( j ) ? Di sini ( i , j ) tidak dipesan, yaitu, saya bisa berada di kedua...
Saya mungkin kehilangan sesuatu yang jelas tetapi saya tidak dapat menemukan referensi tentang kompleksitas penghitungan pencocokan (bukan pencocokan sempurna) dalam grafik bipartit. Inilah masalah formal: Input: grafik bipartit denganG=(U,V,E)G=(U,V,E)G = (U, V, E)E⊆U×VE⊆U×VE \subseteq U \times...
Saya memiliki satu set agen dan satu set n tugas, dan saya perlu menetapkan masing-masing agen dengan tepat satu tugas sehingga biaya diminimalkan. Beberapa agen tidak kompatibel dengan beberapa tugas.nnnnnn Saya memiliki implementasi Algoritma Hongaria yang membutuhkan waktu sekitar satu menit...
Pertimbangkan grafik berbobot dengan beberapa tepi merah. Kami tertarik untuk menemukan pencocokan sempurna, sehingga jumlah tepi merah rata, dan di bawah kendala sebelumnya, berat diminimalkan. Apakah masalah ini dapat diselesaikan dalam waktu polinomial? Bahkan untuk grafik bipartit? Bagaimana...