Finden Sie alle chordless Zyklen in ungerichteten Graphen

So finden Sie alle chordless Zyklen in einem ungerichteten Graphen?

Beispielsweise angesichts der graph

0 --- 1
|     | \
|     |  \
4 --- 3 - 2

sollte der Algorithmus zurück 1-2-3 und 0-1-3-4, aber nie 0-1-2-3-4.


(Hinweis: [1] Diese Frage ist nicht das gleiche wie die kleine-Zyklus finden in einem planaren Graphen, weil der graph nicht notwendigerweise planar. [2] ich habe gelesen das Papier Erzeugen alle Zyklen, chordless Zyklen, und Hamilton-Zyklen mit dem Prinzip der Ausgrenzung aber ich verstehe nicht, was Sie tun :). [3] ich habe versucht CYPATH aber das Programm gibt nur die Anzahl, Algorithmus EnumChordlessPath in readme.txt hat erhebliche Tippfehler, und der C-code ist ein Chaos. [4] ich bin nicht versuchen zu finden, einen beliebigen Satz von fundametal Zyklen. Zyklus haben können Akkorde.)

  • Keine Einschränkung, aber das wäre zu ineffizient.
  • Ich habe nicht viel gutes tun, veröffentlichen Sie einen link zu einem paper hinter einer paywall.
  • manchmal ist es nicht -- Verweise auf Papiere sind nützlich, + ACM ist nicht genau einer obskuren Fachzeitschrift. (obwohl ich don ' T haben Zugang zu Ihr)
  • Gibt es mehr als einen Weg, der Bau von Rad-Basen? Etwas scheint faul hier... sieht aus wie chordless Zyklen bilden eine basis, aber ich könnte etwas fehlen offensichtlich.
  • ja. Betrachten Sie das komplette 4-Graphen, die hat 4 verschiedene Möglichkeiten zur Auswahl einer basis (3 Dreiecke). Es kann mehr chordless Zyklen als die Anzahl der basis.
  • Warum ist ein math.sx-moderator, diese Frage hier? Sind Sie nach Implementierungen? Frage: "gibt es irgendwelche interessanten Eigenschaften der Klasse von chordless Diagramme, die mir helfen würden, generieren Sie effizient?" klingt wie ein nützlicher Ausgangspunkt für mich, da es scheint, dass Ihre motivation ist, um ein Gefühl für die Suche nach Raum, nicht nur werfen gemeinsam einen hack.
  • Natürlich bin ich nach der Durchführung, oder ein Algorithmus, der geschrieben ist in pseudo-code, der einfach umgesetzt werden können.
  • Ich hatte nicht darauf geachtet, um das [language-agnostic] - tag, sorry. Aber wenn Sie kümmern sich um Umsetzung, nicht Sie haben eine Art worst-case-performance-Einschränkung beachten? aioobe die Lösung ist nur in EXPTIME, das ist durchaus machbar, wenn n begrenzt ist durch eine kleine Konstante...
  • Wie unterscheidet sich dies von der Suche nach dem minimum cycle basis eines Graphen? (stackoverflow.com/questions/16782898/...)
  • Dies könnte nützlich sein: arxiv.org/pdf/1309.1051.pdf

InformationsquelleAutor kennytm | 2010-10-26
Schreibe einen Kommentar