Implementierter Code zur Berechnung der Pfadbreite (= Knotensuchnummer, Scheitelpunkttrennungsnummer, Intervalldicke)

13

Ich suche nach einer Implementierung eines Algorithmus zur Berechnung der Pfadbreite eines Graphen. Es ist bekannt, dass das Berechnen der Pfadbreite dem Berechnen der Knotensuchnummer, der Scheitelpunkttrennungsnummer oder der Intervalldicke des Graphen äquivalent ist. Der Algorithmus muss nicht sehr schnell sein; Ich möchte es auf Graphen von höchstens 20 Eckpunkten ausführen. Ich benötige den Algorithmus, um die Pfadbreite genau zu berechnen, anstatt eine Annäherung zu geben.

Ich bin mir bewusst, dass es einige Implementierungen gibt, mit denen die Baumbreite eines Graphen berechnet werden kann (ein verwandtes Konzept), aber bisher keine gefunden wurden, mit denen die Pfadbreite berechnet werden kann. Hinweise sind willkommen!

ds.algorithms reference-request graph-algorithms implementation Bart Jansen
quelle

Antworten:

8

Eine einfache DFS + DP-Implementierung wurde letztes Jahr zu SAGE 4.8 hinzugefügt: sage.graphs.graph_decompositions.vertex_separation.path_decomposition

Es ist hier und hier in Cython (GNU GPL) implementiert . Sehr einfach und kurz, wenn Sie alles Unnötige ignorieren. Zeit mit ω = p w ( G ) . Es könnte mit Schnittregeln und insbesondere einer Heuristik beschleunigt werden.Ö(nω2n)ω=pw(G)

Ralph Versteegen
quelle
Wouaaaaaaaahhhh !! Wie haben Sie erfahren, dass es zu Sage hinzugefügt wurde? Schön zu sehen, dass die Leute tatsächlich sehen, welche neuen Funktionen Sage bietet :-)
Nathann Cohen
Übrigens ist die Dokumentation des Moduls einfach da und erklärt, wie alles funktioniert: sagemath.org/doc/reference/sage/graphs/graph_decompositions/…
Nathann Cohen
Es tut mir leid, Sie zu enttäuschen, aber ich bin eigentlich kein SAGE-Benutzer. Google hat festgestellt, dass Ihr Patch dazu beigetragen hat. Ich würde zu SAGE beitragen (ich benutze bereits Cython), aber ich denke, es wäre besser, zu vorgelagerten Projekten (NetworkX?) Beizutragen, in denen mehr Menschen davon Gebrauch machen können.
Ralph Versteegen
Gut. NetworkX ist nicht mehr wirklich "upstream" von Sage, da es NetworkX nicht wirklich viel nutzt, es sei denn, Sie fragen danach. Und die Möglichkeit, andere Teile der Mathematik zu verwenden, macht Cython und die Schnittstelle zur linearen Programmierung auch einen Unterschied :-P
Nathann Cohen
8

Keine Ahnung von "einer Implementierung", aber check out

Berechnen der Pfadbreite schneller als 2 ^ n Karol Suchan und Yngve Villanger Parametrisierte und exakte Berechnung, 4. Internationaler Workshop, IWPEC 2009, Kopenhagen, Dänemark, Springer Verlag, Lecture Notes in Computer Science 5917, Seiten 324-335.

Andreas Björklund
quelle
2

Hisao Tamaki hat kürzlich einen genauen Algorithmus für die gerichtete Pfadbreite entwickelt (WG 2011). Dort bezieht er sich auf eine erfolgreiche praktische Anwendung seines Ansatzes (ISCIT 2010). Ich denke, er hat auch eine Implementierung des Algorithmus.

Hisao Tamaki: Ein gerichteter Pfadzerlegungsansatz zur exakten Identifizierung von Attraktoren boolescher Netzwerke. Internationales Symposium für Kommunikations- und Informationstechnologien (ISCIT 2010), S. 844-849

Hisao Tamaki: Ein polynomieller Zeitalgorithmus für begrenzte gerichtete Pfadbreite. In: 37. Internationaler Workshop zu graphentheoretischen Konzepten in der Informatik (WG 2011), LNCS 6986, S. 331-342.

Hermann Gruber
quelle