Fibonacci-Haufen – Enzyklopädie

Fibonacci-Haufen
Typ Haufen
Erfunden 1984
Erfunden von Michael L. Fredman und Robert Endre Tarjan
Zeitkomplexität in Big O-Notation
Algorithmus Durchschnitt Schlimmster Fall
Einfügen Θ (1)
Find-min Θ (1)
Delete-min O (log n )
Verkleinerungsschlüssel Θ (1)
Zusammenführen Θ (1)

In der Informatik ist ein Fibonacci-Heap eine Datenstruktur für Prioritätswarteschlangenoperationen, die aus einer Sammlung von Heap-geordneten Bäumen besteht . Die Laufzeit ist amortisierter als bei vielen anderen Warteschlangendatenstrukturen mit Priorität, einschließlich Binär- und Binomial-Heap. Michael L. Fredman und Robert E. Tarjan entwickelten 1984 Fibonacci-Haufen und veröffentlichten sie 1987 in einer wissenschaftlichen Zeitschrift. Fibonacci-Haufen sind nach den Fibonacci-Zahlen benannt, die in ihrer Laufzeitanalyse verwendet werden.

Für den Fibonacci-Heap dauert die Find-Minimum-Operation eine konstante ( O (1)) amortisierte Zeit. [1] Die Tastenoperationen Einfügen und Verringern funktionieren auch in einer konstanten amortisierten Zeit. [2] Löschen Ein Element (das am häufigsten im Sonderfall des Löschens des Minimalelements verwendet wird) arbeitet in O (log n ), wobei n die Größe von ist der Haufen. [2] Dies bedeutet, dass ausgehend von einer leeren Datenstruktur jede Folge von a Einfügen und Verringern von Schlüsseloperationen und b Löschen von Operationen O ( a + b log n ) Worst-Case-Zeit, wobei n die maximale Heap-Größe ist. In einem binären oder binomialen Haufen würde eine solche Folge von Operationen 0 ( a + b ) log n ) Zeit in Anspruch nehmen. Ein Fibonacci-Heap ist also besser als ein binärer oder binomischer Heap, wenn b um einen nicht konstanten Faktor kleiner als a ist. Es ist auch möglich, zwei Fibonacci-Heaps in konstanter, amortisierter Zeit zusammenzuführen, wodurch die logarithmische Zusammenführungszeit eines Binomial-Heaps und Binär-Heaps, die Zusammenführungen nicht effizient verarbeiten können, verbessert werden.

Die Verwendung von Fibonacci-Heaps für Prioritätswarteschlangen verbessert die asymptotische Laufzeit wichtiger Algorithmen, z. B. des Dijkstra-Algorithmus zur Berechnung des kürzesten Pfads zwischen zwei Knoten in einem Diagramm, im Vergleich zum gleichen Algorithmus unter Verwendung anderer Warteschlangendatenstrukturen mit niedrigerer Priorität.

Struktur [ Bearbeiten

Abbildung 1. Beispiel eines Fibonacci-Haufens. Es hat drei Bäume der Grade 0, 1 und 3. Drei Eckpunkte sind markiert (blau dargestellt). Daher beträgt das Potenzial des Haufens 9 (3 Bäume + 2 × (3 markierte Scheitelpunkte)).

Ein Fibonacci-Haufen ist eine Sammlung von Bäumen, die die Minimum-Heap-Eigenschaft erfüllen, dh der Schlüssel eines Kindes ist Immer größer oder gleich dem Schlüssel des übergeordneten Elements. Dies impliziert, dass sich der Mindestschlüssel immer an der Wurzel eines der Bäume befindet. Im Vergleich zu Binomialhaufen ist die Struktur eines Fibonacci-Haufens flexibler. Die Bäume haben keine vorgeschriebene Form und im Extremfall kann der Haufen jedes Element in einem separaten Baum haben. Durch diese Flexibilität können einige Vorgänge auf träge Weise ausgeführt werden, wodurch die Arbeit für spätere Vorgänge verschoben wird. Das Zusammenführen von Heaps erfolgt beispielsweise einfach durch Verketten der beiden Baumlisten, und die Operation Schlüssel verringern schneidet manchmal einen Knoten von seinem übergeordneten Knoten aus und bildet einen neuen Baum.

Irgendwann muss jedoch eine Reihenfolge in den Heap eingefügt werden, um die gewünschte Laufzeit zu erreichen. Insbesondere werden Knotengrade (Grad bedeutet hier die Anzahl der Kinder) relativ niedrig gehalten: Jeder Knoten hat höchstens einen Grad O (log n ) und die Größe eines Teilbaums, der verwurzelt ist in einem Gradknoten k ist mindestens F k +2 wobei F k das k ist die Fibonacci-Nummer. Dies wird durch die Regel erreicht, dass wir höchstens ein Kind von jedem Nicht-Root-Knoten schneiden können. Wenn ein zweites untergeordnetes Element ausgeschnitten wird, muss der Knoten selbst von seinem übergeordneten Element abgeschnitten werden und wird zur Wurzel eines neuen Baums (siehe Nachweis von Gradgrenzen unten). Die Anzahl der Bäume wird in der Operation minimale Streichung verringert, bei der Bäume miteinander verbunden werden.

Aufgrund einer entspannten Struktur können einige Operationen sehr lange dauern, während andere sehr schnell ausgeführt werden. Für die Analyse der amortisierten Laufzeit verwenden wir die potenzielle Methode, indem wir vorgeben, dass sehr schnelle Vorgänge etwas länger dauern als sie tatsächlich dauern. Diese zusätzliche Zeit wird dann später kombiniert und von der tatsächlichen Laufzeit langsamer Operationen abgezogen. Die Zeitersparnis für eine spätere Verwendung wird zu jedem Zeitpunkt durch eine mögliche Funktion gemessen. Das Potenzial eines Fibonacci-Haufens ist gegeben durch

Potential = t + 2 m

wobei t die Anzahl der Bäume im Fibonacci-Haufen ist und m die Anzahl ist von markierten Knoten. Ein Knoten ist markiert, wenn mindestens eines seiner untergeordneten Knoten abgeschnitten wurde, da dieser Knoten zu einem untergeordneten Knoten eines anderen Knotens gemacht wurde (alle Wurzeln sind nicht markiert).
Die amortisierte Zeit für eine Operation ergibt sich aus der Summe der tatsächlichen Zeit und c mal der Potentialdifferenz, wobei c eine Konstante ist (gewählt, um den konstanten Faktoren in O Notation für die aktuelle Zeit).

Somit hat die Wurzel jedes Baums in einem Haufen eine gespeicherte Zeiteinheit. Diese Zeiteinheit kann später verwendet werden, um diesen Baum zum amortisierten Zeitpunkt 0 mit einem anderen Baum zu verknüpfen. Außerdem sind in jedem markierten Knoten zwei Zeiteinheiten gespeichert. Man kann verwendet werden, um den Knoten von seinem Elternknoten zu trennen. In diesem Fall wird der Knoten zur Wurzel und die zweite Zeiteinheit bleibt wie in jeder anderen Wurzel gespeichert.

Implementierung von Operationen [ Bearbeiten

Um ein schnelles Löschen und Verketten zu ermöglichen, werden die Wurzeln aller Bäume über eine kreisförmige, doppelt verknüpfte Liste verknüpft. Die untergeordneten Elemente jedes Knotens werden ebenfalls mithilfe einer solchen Liste verknüpft. Für jeden Knoten pflegen wir die Anzahl der untergeordneten Knoten und ob der Knoten markiert ist. Außerdem pflegen wir einen Zeiger auf die Wurzel, die den Mindestschlüssel enthält.

Die Operation find minimum ist jetzt trivial, da der Zeiger auf den Knoten, der sie enthält, beibehalten wird. Das Potenzial des Haufens ändert sich nicht, daher sind sowohl die tatsächlichen als auch die fortgeführten Anschaffungskosten konstant.

Wie oben erwähnt, wird Merge einfach durch Verketten der Baumwurzellisten der beiden Haufen implementiert. Dies kann in konstanter Zeit erfolgen und das Potenzial ändert sich nicht, was wiederum zu einer konstanten Amortisationszeit führt.

Operation insert erstellt einen neuen Heap mit einem Element und führt die Zusammenführung durch. Dies dauert konstant und das Potenzial steigt um eins, da die Anzahl der Bäume zunimmt. Die fortgeführten Anschaffungskosten sind somit weiterhin konstant.

Operation Mindestauszug (wie Mindestauszug ) erfolgt in drei Phasen. Zuerst nehmen wir die Wurzel, die das minimale Element enthält und entfernen es. Seine Kinder werden Wurzeln neuer Bäume. Wenn die Anzahl der Kinder d war, dauert es O ( d ), um alle neuen Wurzeln zu verarbeiten, und das Potenzial steigt um d −1. Daher beträgt die abgeschriebene Laufzeit dieser Phase O ( d ) = O (log n ).

Um die Operation zum Extrahieren des Minimums abzuschließen, müssen wir den Zeiger auf den Stamm mit dem Minimumschlüssel aktualisieren. Leider kann es bis zu n Wurzeln geben, die wir überprüfen müssen. In der zweiten Phase verringern wir daher die Anzahl der Wurzeln, indem wir nacheinander Wurzeln gleichen Grades miteinander verbinden. Wenn zwei Wurzeln u und v den gleichen Grad haben, machen wir eine von ihnen zu einem Kind der anderen, so dass die mit dem kleineren Schlüssel die Wurzel bleibt. Sein Grad erhöht sich um eins. Dies wird wiederholt, bis jede Wurzel einen anderen Grad hat. Um Bäume des gleichen Grades effizient zu finden, verwenden wir ein Array der Länge O (log n ), in dem wir einen Zeiger auf eine Wurzel jedes Grades behalten. Wenn ein zweiter Stamm mit dem gleichen Grad gefunden wird, werden die beiden verknüpft und das Array aktualisiert. Die tatsächliche Laufzeit beträgt O (log n + m ), wobei m die Anzahl der Wurzeln zu Beginn der zweiten Phase ist . Am Ende werden wir höchstens O (log n ) Wurzeln haben (weil jede einen anderen Grad hat). Daher ist der Unterschied in der Potentialfunktion von vor dieser Phase zu danach: O (log n ) – m und die amortisierte Laufzeit ist dann höchstens O (log n + m ) + c ( O (log n ) – m ). Bei einer ausreichend großen Auswahl von c vereinfacht sich dies zu O (log n ).

Abbildung 2. Fibonacci-Haufen aus Abbildung 1 nach der ersten Phase des Extraktminimums. Knoten mit Schlüssel 1 (das Minimum) wurde gelöscht, und seine Kinder wurden als separate Bäume hinzugefügt.

Abbildung 3. Fibonacci-Haufen aus Abbildung 1, nachdem das Extraktionsminimum abgeschlossen wurde. Zunächst werden die Knoten 3 und 6 miteinander verbunden. Anschließend wird das Ergebnis mit dem auf Knoten 2 verwurzelten Baum verknüpft. Schließlich wird das neue Minimum gefunden.

Abbildung 4. Fibonacci-Heap von Abbildung 1 nach dem Verringern des Schlüssels von Knoten 9 auf 0. Dieser Knoten sowie seine beiden markierten Vorfahren sind aus dem bei 1 wurzelnden Baum schneiden und als neue Wurzeln setzen.

In der dritten Phase prüfen wir jede der verbleibenden Wurzeln und finden das Minimum. Dies dauert O (log n ) und das Potenzial ändert sich nicht. Die amortisierte Gesamtlaufzeit des Extraktminimums beträgt daher O (log n ).

Operation Schlüssel verkleinern übernimmt den Knoten, verkleinert den Schlüssel und wird die Heap-Eigenschaft verletzt (der neue Schlüssel ist kleiner als der Schlüssel des übergeordneten Elements), wird der Knoten von seinem übergeordneten Element entfernt. Wenn das übergeordnete Element kein Stamm ist, wird es markiert. Wenn es bereits markiert wurde, wird es ebenfalls ausgeschnitten und sein übergeordnetes Element wird markiert. Wir fahren weiter aufwärts, bis wir entweder die Wurzel oder einen nicht markierten Knoten erreichen. Jetzt setzen wir den Minimalzeiger auf den verringerten Wert, wenn es sich um das neue Minimum handelt. Dabei erzeugen wir eine Anzahl von neuen Bäumen, sagen wir k . Jeder dieser neuen Bäume, außer möglicherweise der erste, wurde ursprünglich markiert, aber als Wurzel wird er nicht markiert. Ein Knoten kann markiert werden. Daher ändert sich die Anzahl der markierten Knoten um – ( k – 1) + 1 = – k + 2. Durch Kombination dieser beiden Änderungen ändert sich das Potenzial um 2 (- k + 2) + k = – k + 4. Die tatsächliche Zeit für die Durchführung des Schnitts betrug O ( k ), daher ist (wiederum mit einer ausreichend großen Auswahl von c ) die amortisierte Laufzeit konstant.

Schließlich kann die Operation delete einfach durch Verringern des Schlüssels des zu löschenden Elements auf minus unendlich implementiert werden, wodurch es in das Minimum des gesamten Heaps verwandelt wird. Dann rufen wir das minimale Extrakt auf, um es zu entfernen. Die amortisierte Laufzeit dieses Vorgangs beträgt O (log n ).

Nachweis von Gradgrenzen Bearbeiten

Die amortisierte Leistung eines Fibonacci-Haufens hängt vom Grad (Anzahl der Kinder) eines Baumwurzels ab, der O ist. (log n ), wobei n die Größe des Haufens ist. Hier zeigen wir, dass die Größe des (Unter-) Baums, der an einem beliebigen Knoten x Grad d im Heap wurzelt, mindestens F d [19659060betragenmuss] +2 wobei F k die k te Fibonacci-Zahl ist. Der Grad der Bindung folgt daraus und der Tatsache (leicht durch Induktion bewiesen), dass

F d + 2 φ d { displaystyle F_ {d + 2} geq varphi ^ {d}}

für alle ganzen Zahlen

d 0 { displaystyle d geq 0}

wobei

φ = ( 1 ] + 5 ) / 2 1.618 { displaystyle varphi = (1 + { sqrt {5}}) / 2 doteq 1.618}

. (Wir haben dann

n F d + 2 φ d { displaystyle n geq F_ {d + 2} geq varphi ^ {d}}

und das Protokoll zur Basis nehmen

φ { displaystyle varphi}

auf beiden Seiten ergibt

d log φ n displaystyle d leq log _ { varphi} n}

nach Bedarf.)

Betrachten Sie einen Knoten x irgendwo auf dem Haufen ( x muss nicht die Wurzel eines der Hauptbäume sein). Definieren Sie Größe ( x ) als die Größe des Baumes, dessen Wurzel x ist (die Anzahl der Nachkommen von x einschließlich ) ] x selbst). Wir beweisen durch Induktion auf der Höhe von x (der Länge eines längsten einfachen Weges von x zu einem nachkommenden Blatt), dass Größe ( x ) ≥ F d +2 wobei d der Grad von x ist.

Basisfall: Wenn x die Höhe 0 hat, dann d = 0 und Größe ( x ]) = 1 = F 2 .

Induktiver Fall: Angenommen, x hat eine positive Höhe und einen positiven Grad d > 0. Sei y 1 y 2 y d die Kinder von x indiziert nach der Zeit, in der sie zuletzt Kinder von x ( y 1 wurden, wobei y d der früheste war spätestens), und seien c 1 c 2 c d ihre jeweiligen Grade. Wir behaupten dass c i i -2 für jedes i mit 2 ≤ i d : Kurz vor y i wurde ein Kind von x y 1 y i −1 waren bereits Kinder von x und so hatte x einen Abschluss von mindestens i −1 zu dieser Zeit. Da Bäume nur dann kombiniert werden, wenn die Grade ihrer Wurzeln gleich sind, muss es gewesen sein, dass y i zu dem Zeitpunkt, als es a wurde, auch einen Grad von mindestens i -1 hatte Kind von x . Von dieser Zeit bis zur Gegenwart kann y i nur höchstens ein Kind verloren haben (wie durch das Markierungsverfahren garantiert), und daher ist sein derzeitiger Abschluss c i ] ist mindestens i −2. Dies beweist die Behauptung .

Da die Höhen aller y i streng kleiner sind als die von x können wir die induktive Hypothese auf sie anwenden, um Größe [19459016zuerhalten] ( y i ) ≥ F c i +2 F ( i – 2) + 2 = F i . Die Knoten x und y 1 tragen jeweils mindestens 1 zur Größe ( x ) bei

Größe ( x ) 2 + i = 2 d size ( y i ) ] ≥ 2 + i = 2 d F i = 1 19659082] + i = 0 d F i . { displaystyle { textbf {size} (x ) geq 2+ sum _ {i = 2} ^ {d} { textbf {size}} (y_ {i}) geq 2+ sum _ {i = 2} ^ {d} F_ {i} = 1 + sum _ {i = 0} ^ {d} F_ {i}.}

Eine Routineinduktion beweist, dass

1 + i = 0 d F i = ] F d + 2 { displaystyle 1+ sum _ {i = 0} ^ {d} F_ {i} = F_ {d + 2}}

für jeden

d 0 { displaystyle d geq 0}

was die gewünschte Untergrenze für die Größe ( x ) ergibt.

Worst Case [ Bearbeiten

Obwohl Fibonacci-Haufen sehr effizient aussehen, weisen sie die folgenden zwei Nachteile auf (wie in der Veröffentlichung "The Pairing Heap: A new form of Self Adjusting" erwähnt) Heap "):" Sie sind kompliziert in der Codierung. Außerdem sind sie in der Praxis weniger effizient als die theoretisch weniger effizienten Formen von Heaps, da sie in ihrer einfachsten Version die Speicherung und Bearbeitung von vier Zeigern pro Knoten erfordern. im Vergleich zu den zwei oder drei Zeigern pro Knoten, die für andere Strukturen benötigt werden ". [3] Diese anderen Strukturen werden als Binärhaufen, Binomialhaufen, Paarungshaufen, Brodalhaufen und Rangpaarungshaufen bezeichnet.

Obwohl die Gesamtlaufzeit einer Sequenz von Operationen, die mit einer leeren Struktur beginnen, durch die oben angegebenen Grenzen begrenzt ist, können einige (sehr wenige) Operationen in der Sequenz sehr lange dauern, bis sie abgeschlossen sind (insbesondere müssen Lösch- und Löschminimum linear sein Laufzeit im schlimmsten Fall). Aus diesem Grund sind Fibonacci-Heaps und andere amortisierte Datenstrukturen möglicherweise nicht für Echtzeitsysteme geeignet. Es ist möglich, eine Datenstruktur zu erstellen, die die gleiche Leistung im ungünstigsten Fall aufweist, wie der Fibonacci-Heap die Leistung amortisiert hat. Eine solche Struktur, die Brodal-Warteschlange [4] ist nach den Worten des Schöpfers "ziemlich kompliziert" und "[not] in der Praxis anwendbar". Der 2012 erstellte strenge Fibonacci-Haufen [5] ist eine einfachere (im Vergleich zu Brodals) Struktur mit denselben Worst-Case-Grenzen. Es ist nicht bekannt, ob der strenge Fibonacci-Haufen in der Praxis effizient ist. Die von Driscoll et al. eine gute Worst-Case-Leistung für alle Fibonacci-Heap-Operationen mit Ausnahme von Merge liefern.

Zusammenfassung der Laufzeiten [ ]

Hier sind Zeitkomplexitäten [6] verschiedener Heap-Datenstrukturen. Funktionsnamen setzen einen Min-Heap voraus. Zur Bedeutung von " O ( f )" und " Θ ( f )" siehe Big O-Notation.

Praktische Überlegungen Bearbeiten ]

Fibonacci-Heaps gelten in der Praxis als langsam [14] da sie viel Speicher pro Knoten und eine hohe Konstante benötigen Faktoren für alle Operationen. [15] Jüngste experimentelle Ergebnisse legen nahe, dass Fibonacci-Haufen in der Praxis effizienter sind als die meisten späteren Derivate, einschließlich Beben-Haufen, Verstoß-Haufen, strenger Fibonacci-Haufen, Rang-Paar-Haufen, aber weniger effizient als entweder Paar-Haufen oder Array-basierte Haufen. [16]

Referenzen [ edit ]

  1. ^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "Kapitel 20: Fibonacci-Haufen". Einführung in Algorithmen (2. Aufl.). MIT Press und McGraw-Hill. S. 476–497. ISBN 0-262-03293-7 . Dritte Auflage S. 518.
  2. ^ a b c Fredman, Michael Lawrence; Tarjan, Robert E. (Juli 1987). "Fibonacci-Heaps und ihre Verwendung in verbesserten Algorithmen zur Netzwerkoptimierung" (PDF) . Zeitschrift der Association for Computing Machinery . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . doi: 10.1145 / 28869.28874.
  3. ^ Fredman, Michael L .; Sedgewick, Robert; Sleator, Daniel D .; Tarjan, Robert E. (1986). "Der Paarungshaufen: eine neue Form des sich selbst anpassenden Haufens" (PDF) . Algorithmica . 1 (1): 111–129. doi: 10.1007 / BF01840439.
  4. ^ Gerth Stølting Brodal (1996), "Worst-Case Efficient Priority Queues", Proc. 7. ACM-SIAM-Symposium zu diskreten Algorithmen Gesellschaft für industrielle und angewandte Mathematik: 52–58, CiteSeerX 10.1.1.43.8133 doi: 10.1145 / 313852.313883, ISBN 0-89871- 366-8
  5. ^ Brodal, GSL; Lagogiannis, G; Tarjan, R. E. (2012). Strenge Fibonacci-Haufen (PDF) . Vorträge des 44. Symposiums zur Theorie des Rechnens – STOC '12. p. 1177. doi: 10.1145 / 2213977.2214082. ISBN 978-1-4503-1245-5 .
  6. ^ a b c d Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. (1990). Einführung in Algorithmen (1. Aufl.). MIT Press und McGraw-Hill. ISBN 0-262-03141-8 .
  7. ^ Iacono, John (2000), "Verbesserte Obergrenzen für die Paarung von Haufen", Proc. 7. Skandinavischer Workshop zur Algorithmentheorie (PDF) Lecture Notes in Computer Science, 1851 Springer-Verlag, S. 63–77, arXiv: 1110.4428 CiteSeerX 10.1.1.748.7812 doi: 10.1007 / 3-540-44985-X_5, ISBN 3-540-67690-2
  8. ^ Fredman, Michael Lawrence (Juli 1999). "Über die Effizienz der Paarung von Haufen und verwandten Datenstrukturen" (PDF) . Zeitschrift der Association for Computing Machinery . 46 (4): 473–501. doi: 10.1145 / 320211.320214.
  9. ^ Pettie, Seth (2005). Auf dem Weg zu einer endgültigen Analyse von Paarungshaufen (PDF) . FOCS '05 Proceedings of the 46. Annual IEEE Symposium on Foundations of Computer Science. S. 174–183. CiteSeerX 10.1.1.549.471 . doi: 10.1109 / SFCS.2005.75. ISBN 0-7695-2468-0 .
  10. ^ Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF) Proc. 7. jährliches ACM-SIAM-Symposium über diskrete Algorithmen S. 52–58
  11. ^ Goodrich, Michael T .; Tamassia, Roberto (2004). "7.3.6. Bottom-Up-Heap-Konstruktion". Datenstrukturen und Algorithmen in Java (3. Aufl.). S. 338–341. ISBN 0-471-46983-1 .
  12. ^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rangpaarungshaufen" (PDF) . SIAM J. Computing . 40 (6): 1463–1485. doi: 10.1137 / 100785351.
  13. ^ Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strenge Fibonacci-Haufen (PDF) . Vorträge des 44. Symposiums zur Theorie des Rechnens – STOC '12. S. 1177–1184. CiteSeerX 10.1.1.233.1740 . doi: 10.1145 / 2213977.2214082. ISBN 978-1-4503-1245-5 .
  14. ^ http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/FibonacciHeaps.pdf, p . 79
  15. ^ http://web.stanford.edu/class/cs166/lectures/07/Small07.pdf, p. 72
  16. ^ Larkin, Daniel; Sen, Siddhartha; Tarjan, Robert (2014). "Eine empirische Back-to-Basics-Studie zu Priority Queues". Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments : 61–72. arXiv: 1403.0252 . doi: 10.1137 / 1.9781611973198.7.

Externe Links [ bearbeiten ]


Leave a Reply

Your email address will not be published. Required fields are marked *