Une bonne bibliothèque pour tester si un mineur existe dans un graphique?

18

Je voudrais savoir s'il existe des bibliothèques de graphiques gratuites pour tester si un ensemble spécifique de mineurs existe dans un graphique donné?

graph-algorithms implementation graph-minor Hooman
la source
4
Je souhaite que ! ce serait un excellent papier ou ensemble de papiers ALENEX / SEA.
Suresh Venkat

Réponses:

5

NAUTY peut être utilisé comme une bibliothèque pour vous aider à créer une table de hachage pour l'ensemble des mineurs de graphes pour les petits . La clé serait la forme canonique donnée par NAUTY et la valeur serait une concaténation dans l'ordre trié des formes canoniques de ses mineurs directs.n

Chad Brewbaker
la source
Oui, mais nauty ne fournit (pour autant que je sache) aucune méthode pour trouver des mineurs en premier lieu . De plus, étant donné que la question portait uniquement sur la présence / l'absence d'un ensemble spécifique de mineurs, je ne vois pas comment la création d'une table de hachage à partir de toutes les instances aide à résoudre ce problème initial ...
Joshua Grochow
Wendy Myrvold et Brendan McKay font beaucoup de recherches mineures sur les graphiques avec NAUTY comme bibliothèque de support. DFS sur les suppressions / jointures jusqu'à ce que vous atteigniez un nombre traitable de sommets, puis interrogez le poset pré-calculé. La façon dont vous effectuez le DFS dépendra du type de mineur que vous recherchez.
Chad Brewbaker
Intéressant! Vous devriez faire cette partie de la réponse. Pouvez-vous également donner une référence? Je ne l'ai pas trouvé.
Joshua Grochow