Saya mencari implementasi algoritma untuk menghitung jalur lebar grafik. Telah diketahui bahwa menghitung lebar jalur setara dengan menghitung angka pencarian simpul, angka pemisahan titik, atau ketebalan interval grafik. Algoritma tidak harus sangat cepat; Saya ingin menjalankannya pada grafik paling banyak 20 simpul. Saya memang membutuhkan algoritma untuk menghitung pathwidth dengan tepat, daripada memberikan perkiraan.
Saya sadar bahwa ada beberapa implementasi untuk menghitung treewidth dari grafik (konsep terkait) tetapi belum dapat menemukan apapun untuk menghitung jalur lebar. Setiap petunjuk dihargai!
Tidak tahu tentang "implementasi" tetapi periksa
Komputasi Pathwidth Lebih Cepat Dari 2 ^ Karol Suchan dan Yngve Villanger Parameterisasi dan Persis Perhitungan Tepat, Lokakarya Internasional ke-4, IWPEC 2009, Kopenhagen, Denmark, Springer Verlag, Catatan Kuliah di Ilmu Komputer 5917, Halaman 324-335.
sumber
Hisao Tamaki baru-baru ini merancang algoritma yang tepat untuk bandwidth yang diarahkan (WG 2011). Di sana ia merujuk pada beberapa aplikasi praktis yang berhasil dari pendekatannya (ISCIT 2010), jadi saya kira ia juga memiliki implementasi algoritma.
Hisao Tamaki: Suatu pendekatan dekomposisi jalur terarah untuk mengidentifikasi secara tepat para penarik jaringan boolean. Simposium Internasional tentang Teknologi Komunikasi dan Informasi (ISCIT 2010), hlm. 844-849
Hisao Tamaki: Algoritma Waktu Polinomial untuk Pathwidth Berarah Terbatas. Dalam: Lokakarya Internasional ke-37 tentang Konsep Grafik-Teori dalam Ilmu Komputer (WG 2011), LNCS 6986, hlm. 331-342.
sumber