Uma boa biblioteca para testar se existe um menor em um gráfico?

Gostaria de saber se existem bibliotecas de gráficos gratuitas para testar se existe um conjunto específico de menores em um determinado gráfico?

graph-algorithms implementation graph-minor Hooman
fonte

Eu gostaria ! esse seria um excelente papel ou conjunto de papéis ALENEX / SEA.

Suresh Venkat 23/02

Respostas:

O NAUTY pode ser usado como uma biblioteca para ajudá-lo a criar uma tabela de hashtags para todo o grupo de menores de gráfico para pequenos . A chave seria a forma canonial dada por NAUTY e o valor seria uma concatenação em ordem classificada das formas canônicas de seus menores diretos. $n$

Chad Brewbaker
fonte

Sim, mas nauty (até onde eu sei) não fornece nenhum método para encontrar menores em primeiro lugar . Além disso, dado que a pergunta foi sobre meramente a presença / ausência de um conjunto específico de menores, eu não vejo como a construção de um fora hashtable de todas as instâncias ajuda a resolver esse problema inicial ...

Joshua Grochow

Wendy Myrvold e Brendan McKay fazem muitas pesquisas menores com o NAUTY como uma biblioteca de suporte. DFS em exclusões / junções até chegar a um número tratável de vértices e, em seguida, consulte o poset pré-calculado. Como você faz o DFS dependerá do tipo de menor que você está procurando.

Chad Brewbaker

Interessante! Você deve fazer parte da resposta. Além disso, você pode dar uma referência? Não consegui encontrar.

Joshua Grochow