Perpustakaan yang baik untuk menguji apakah ada anak di bawah umur dalam grafik?

Saya ingin tahu apakah ada perpustakaan grafik gratis untuk menguji apakah ada sekelompok anak di bawah umur yang ada dalam grafik tertentu?

graph-algorithms implementation graph-minor Hooman
sumber

Saya harap ! itu akan menjadi kertas ALENEX / LAUT yang sangat baik atau set kertas.

Suresh Venkat

Jawaban:

NAUTY dapat digunakan sebagai perpustakaan untuk membantu Anda membangun hashtable untuk seluruh poset grafik anak di bawah umur untuk kecil . Kuncinya adalah bentuk kanonik yang diberikan oleh NAUTY dan nilainya akan menjadi gabungan dari urutan bentuk kanonis dari anak di bawah umur langsungnya. $n$

Chad Brewbaker
sumber

Ya, tapi nauty tidak (sejauh yang saya tahu) memberikan metode apa pun untuk menemukan anak di bawah umur . Juga, mengingat bahwa pertanyaannya adalah hanya tentang ada / tidaknya seperangkat anak di bawah umur tertentu, saya tidak melihat bagaimana membangun hashtable dari semua contoh membantu menyelesaikan masalah awal ...

Joshua Grochow

Wendy Myrvold dan Brendan McKay melakukan banyak penelitian grafik kecil dengan NAUTY sebagai perpustakaan pendukung. DFS pada penghapusan / bergabung sampai Anda turun ke sejumlah titik yang bisa ditelusur kemudian kueri poset pra-dihitung. Bagaimana Anda melakukan DFS akan tergantung pada jenis minor apa yang Anda cari.

Chad Brewbaker

Menarik! Anda harus membuat bagian dari jawaban itu. Bisakah Anda memberikan referensi? Saya tidak dapat menemukannya.

Joshua Grochow