Ich versuche, die gemeinsamen Knoten zu finden, die immer von jedem möglichen Pfad in einem zyklisch gerichteten Graphen besucht werden. Meine Idee wäre, alle möglichen Pfade zu berechnen und dann nach den gemeinsamen Elementen zu suchen. Jedoch a) das scheint nicht sehr effizient zu sein und b) es Zyklen nicht berücksichtigt.Finden Sie den gemeinsamen Pfad unter allen möglichen Pfaden in einem gerichteten Diagramm
Das Ziel: ist oblivious hashing perimeter als eine manipulationssichere Methode zu implementieren. Dafür muss ich eine Menge allgemeiner Basisblöcke identifizieren, die in einem Kontrollflussgraphen eingegeben werden. Mit anderen Worten, ich möchte deterministische Teile eines Programms (Satz von Basisblöcken) finden, die für jede gegebene Eingabe ausgeführt werden.
'Ich versuche die gemeinsamen Knoten zu finden, die immer von ** jedem möglichen Pfad ** in einem zyklisch gerichteten Graphen besucht werden. Das ist eine problematische Aussage. Ein leerer Pfad (Länge 0, von einem Knoten zu sich selbst) ist ebenfalls ein Pfad, und dementsprechend hat kein Knoten (außer einem Graph mit | V | <= 1) einen Knoten, der diese Bedingung erfüllt. Sie müssen die Bedingung "jeden einzelnen Pfad" verfeinern. – amit