Zählen und Finden aller perfekten / maximalen Übereinstimmungen in allgemeinen Diagrammen

8

Vor kurzem habe ich mich mit einem Problem befasst, das mich zu folgenden Fragen geführt hat:

  • Gibt es einen guten Algorithmus, um alle maximalen / perfekten Übereinstimmungen in einem allgemeinen Diagramm aufzulisten?
  • Gibt es einen guten Algorithmus, um alle maximalen / perfekten Übereinstimmungen in einem allgemeinen Diagramm zu finden?
  • Sind diese beiden Probleme in ihrer Komplexität gleichwertig?

Ich bin auf folgende Referenzen gestoßen:

  • Algorithmen zum Auflisten aller perfekten maximalen und maximalen Übereinstimmungen in zweigeteilten Diagrammen - Vorschlag eines Algorithmus zum Auflisten aller maximalen Übereinstimmungen in einem zweigeteilten Diagramm.
  • Finden aller perfekten Übereinstimmungen in zweigeteilten Graphen - Vorschlag eines Algorithmus zum Finden aller perfekten Übereinstimmungen in zweigeteilten Graphen

Die Komplexität beider Algorithmen hängt von der Anzahl der perfekten Übereinstimmungen im Diagramm ab (was im schlimmsten Fall eine exponentielle Laufzeit bedeutet).

Darüber hinaus befassen sich beide Artikel mit zweigeteilten Diagrammen. Ich konnte keine ähnlichen Artikel finden, die sich mit demselben Problem in allgemeinen Diagrammen befassen.

Ich würde mich über Informationen und Referenzen zu den oben genannten Problemen freuen.

Ron Teller
quelle
Da es bei Ihrer Frage auch darum geht, alle perfekten Übereinstimmungen in einem allgemeinen Diagramm zu finden: Haben Sie zusätzliche Referenzen oder Implementierungen dazu gefunden?
Bonanza

Antworten:

7

#P.#P.. Beide Artikel erwähnen, dass ihre Algorithmen bei zufälligen Graphen gut zu funktionieren scheinen, im schlimmsten Fall jedoch nicht unbedingt so gut.

#P.

Yuval Filmus
quelle