¿Una buena biblioteca para probar si existe un menor en un gráfico?

Me gustaría saber si hay bibliotecas de gráficos gratuitas para probar si existe un conjunto específico de menores en un gráfico determinado.

graph-algorithms implementation graph-minor Hooman
fuente

Yo deseo ! ese sería un excelente documento o conjunto de documentos ALENEX / SEA.

Suresh Venkat

Respuestas:

NAUTY se puede usar como una biblioteca para ayudarlo a construir una tabla hash para todo el conjunto de menores de gráficos para pequeños . La clave sería la forma canónica dada por NAUTY y el valor sería una concatenación en orden ordenado de las formas canónicas de sus menores directos. $n$

Chad Brewbaker
fuente

Sí, pero nauty no proporciona (hasta donde yo sé) ningún método para encontrar menores en primer lugar . Además, dado que la pregunta era simplemente sobre la presencia / ausencia de un conjunto específico de menores, no veo cómo construir una tabla hash de todas las instancias ayuda a resolver ese problema inicial ...

Joshua Grochow

Wendy Myrvold y Brendan McKay realizan una gran cantidad de investigaciones gráficas menores con NAUTY como biblioteca de soporte. DFS en eliminaciones / uniones hasta que llegue a un número manejable de vértices y luego consulte el poset calculado previamente. La forma en que realice el DFS dependerá del tipo de menor que esté buscando.

Chad Brewbaker

¡Interesante! Deberías hacer esa parte de la respuesta. Además, ¿puedes dar una referencia? No pude encontrarlo.

Joshua Grochow