Diskussion:Cuthill-McKee-Algorithmus

NP-Vollständigkeit

Letzter Kommentar: vor 11 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

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))Beantworten

Bild

Letzter Kommentar: vor 3 Jahren2 Kommentare2 Personen sind an der Diskussion beteiligt

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))Beantworten

Das fragte ich mich auch. Lichtkind (Diskussion) 23:28, 12. Jun. 2021 (CEST)Beantworten

Startknoten

Letzter Kommentar: vor 4 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

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))Beantworten

Abschnitt hinzufügen