Diskussion:Cuthill-McKee-Algorithmus
NP-Vollständigkeit[Quelltext bearbeiten]
Ein Link oder eine Erklärung, warum die Bestimmung eines peripheren Knotens NP-Vollständig ist, wäre sehr aufschlussreich! Anhand der gegebenen Definition ließe sich das Problem trivial mit einem O(n^3)-Algorithmus (Kürzeste Wege von allen Knoten zu allen Knoten, für jeden Knoten Exzentrität bestimmen, Knoten auswählen) lösen.
Max G. (nicht signierter Beitrag von 31.16.114.33 (Diskussion) 14:17, 21. Dez. 2012 (CET))
Bild[Quelltext bearbeiten]
Sehe ich es richtig, dass das Bild kontextlos ist? Wo ist die ursprüngliche Matrix? (nicht signierter Beitrag von 93.204.3.57 (Diskussion) 16:53, 22. Dez. 2015 (CET))
- Das fragte ich mich auch. Lichtkind (Diskussion) 23:28, 12. Jun. 2021 (CEST)
Startknoten[Quelltext bearbeiten]
Tatsächlich ist das bestimmen eines peripheren Knotens keinesfalls NP-vollständig! Dazu exisieren polynomielle Algorithmen, allerdings dominieren auch diese asymptotisch den RCM-Algorithmus. Deswegen nutzt man pseudoperiphere Knoten, welche man typischerweise deutlich schneller bestimmen kann. NP-vollständig ist die Wahl eines optimalen Startknotens, so dass die Bandbreite optimal minimal wird. Ich werde das ändern. (nicht signierter Beitrag von Lukas Riemer (Diskussion | Beiträge) 09:48, 23. Mär. 2020 (CET))