Diskussion:Cuthill-McKee-Algorithmus

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) Diskussion:Cuthill-McKee-Algorithmus#c-31.16.114.33-2012-12-21T13:17:00.000Z-NP-Vollständigkeit11)Beantworten

Sehe ich es richtig, dass das Bild kontextlos ist? Wo ist die ursprüngliche Matrix? (nicht signierter Beitrag von 93.204.3.57 (Diskussion) Diskussion:Cuthill-McKee-Algorithmus#c-93.204.3.57-2015-12-22T15:53:00.000Z-Bild11)Beantworten

Das fragte ich mich auch. Lichtkind (Diskussion) Diskussion:Cuthill-McKee-Algorithmus#c-Lichtkind-2021-06-12T21:28:00.000Z-93.204.3.57-2015-12-22T15:53:00.000Z11Beantworten

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) Diskussion:Cuthill-McKee-Algorithmus#c-Lukas Riemer-2020-03-23T08:48:00.000Z-Startknoten11)Beantworten