Diberikan keluarga paling banyak himpunan bagian dari . Penutupan serikat adalah himpunan keluarga lain berisi setiap set yang dapat dibangun dengan mengambil serikat dari 1 atau lebih set di . Olehkami menunjukkan jumlah set di .
Apa cara tercepat untuk menghitung penutupan serikat?
Saya telah menunjukkan kesetaraan antara penutupan serikat dan daftar semua set independen maksimal dalam grafik bipartit, oleh karena itu kita tahu bahwa menentukan ukuran penutupan serikat adalah # P-complete.
Namun ada cara untuk membuat daftar semua set independen maksimal (atau klik maksimal) dalam waktu untuk grafik dengan node dan edge Tsukiyama et al. 1977. Tetapi ini tidak khusus untuk grafik bipartit.
Kami memberikan algoritme untuk grafik bipartit dengan runtime http://www.ii.uib.no/~martinv/Papers/BooleanWidth_I.pdf
Metode kami didasarkan pada pengamatan bahwa setiap elemen dalam dapat dibuat dengan penyatuan beberapa elemen lain dari dan salah satu set asli. Karenanya kita akan setiap kali kita menambahkan elemen ke mencoba untuk memperluasnya dengan salah satu dari set asli. Untuk masing-masing set kita perlu memeriksa apakah mereka masih dalam . Kami menyimpan sebagai pohon pencarian biner, sehingga setiap pencarian membutuhkan waktu.
Apakah mungkin untuk menemukan penutupan serikat dalam waktu ? Atau bahkan dalam waktu ?
sumber
Jawaban:
Kompleksitas enumerasi set independen maksimal dalam grafik adalah sama dengan pada grafik bipartit, sehingga bipartiteness tidak membawa sesuatu yang baru.
Anda memiliki algoritme (dengan ruang eksponensial) dalam , tetapi tidak ada algoritme ruang polinomial yang mencapai kompleksitas waktu ini yang diketahui. Makalah berikut ini http://www.sciencedirect.com/science/article/pii/S0166218X08004563 adalah survei yang bagus.O(|C|⋅n2)
sumber