Code implémenté pour calculer la largeur de chemin (= numéro de recherche de nœud, numéro de séparation de vertex, épaisseur d'intervalle)

13

Je recherche une implémentation d'un algorithme pour calculer la largeur de chemin d'un graphe. Il est bien connu que le calcul de la largeur de trajet équivaut au calcul du nombre de recherche de nœuds, du nombre de séparation de sommets ou de l'épaisseur d'intervalle du graphique. L'algorithme n'a pas besoin d'être très rapide; Je veux l'exécuter sur des graphiques d'au plus 20 sommets. J'ai besoin de l'algorithme pour calculer exactement la largeur de chemin, plutôt que de donner une approximation.

Je suis conscient qu'il existe certaines implémentations pour calculer la largeur d'arbre d'un graphique (un concept connexe) mais je n'ai pas pu en trouver pour calculer la largeur de chemin. Tous les pointeurs sont appréciés!

ds.algorithms reference-request graph-algorithms implementation Bart Jansen
la source

Réponses:

8

Une implémentation DFS + DP simple a été ajoutée à SAGE 4.8 l'année dernière: sage.graphs.graph_decompositions.vertex_separation.path_decomposition

Il est implémenté en Cython (GNU GPL) ici et ici . Très simple et court si vous ignorez tout ce qui n'est pas essentiel.O(nω2n) moment où ω=pw(g). Il pourrait être accéléré avec des règles d'élagage, et en particulier une heuristique.

Ralph Versteegen
la source
Wouaaaaaaaaahhhh !! Comment avez-vous appris qu'il a été ajouté à Sage? Ravi de voir que les gens regardent réellement les nouvelles fonctionnalités de Sage :-)
Nathann Cohen
D'ailleurs la documentation du module est juste là, et explique comment tout cela fonctionne: sagemath.org/doc/reference/sage/graphs/graph_decompositions/…
Nathann Cohen
Désolé de décevoir, mais je ne suis pas réellement un utilisateur SAGE; Google a trouvé que votre patch y contribuait. Je contribuerais à SAGE (j'utilise déjà Cython), mais je pense qu'il serait préférable de contribuer à des projets en amont (NetworkX?) Où plus de gens peuvent en faire usage.
Ralph Versteegen
Bien. NetworkX n'est plus vraiment "en amont" de Sage, car il n'utilise pas beaucoup NetworkX à moins que vous ne le demandiez. Et pouvoir utiliser d'autres parties des mathématiques, Cython et l'interface avec la programmation linéaire fait aussi une différence :-P
Nathann Cohen
8

Je ne sais pas "une implémentation" mais vérifiez

Computing Pathwidth Faster Than 2 ^ n Karol Suchan and Yngve Villanger Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhague, Danemark, Springer Verlag, Lecture Notes in Computer Science 5917, Pages 324-335.

Andreas Björklund
la source
2

Hisao Tamaki a récemment conçu un algorithme exact pour la largeur de chemin dirigée (WG 2011). Là, il fait référence à une application pratique réussie de son approche (ISCIT 2010), donc je suppose qu'il a également une implémentation de l'algorithme.

Hisao Tamaki: Une approche dirigée de décomposition de chemin pour identifier exactement les attracteurs des réseaux booléens. Symposium international sur les communications et les technologies de l'information (ISCIT 2010), pp. 844-849

Hisao Tamaki: un algorithme temporel polynomial pour une largeur de chemin dirigée bornée. Dans: 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011), LNCS 6986, pp. 331-342.

Hermann Gruber
la source