Ein Algorithmus zur Ermittlungk-bester Kantenfolgen zwischen allen Ecken eines Graphen

Autor: Beilner, H.
Zdroj: Computing; September 1972, Vol. 10 Issue: 3 p205-220, 16p
Abstrakt: Der Artikel beschreibt ein neues Matrizenverfahren zur Bestimmung der Längen aller besten bisk-besten Kantenfolgen von allenn zu allenn Ecken eines Graphen. Die Besonderheit des Verfahrens liegt darin, daß sich die Maximalzahl benötigter Additionen/Subtraktionen fürn ≫k zu 1/3n5/2k5/2+5n5/2k3/2+0(n3/2k5/2) abschätzen läßt, während die Maximalzahl benötigter Vergleiche wie bei anderen Verfahren in der Größenordnungn3k3 liegt. Der Artikel gibt außerdem einen formalen Beweis der Gültigkeit des Verfahrens und einen kurzen Vergleich mit anderen bekannten Methoden.
Databáze: Supplemental Index
Externí odkaz: