Ungefährer minimalgewichteter Baumzerfall in vollständigen Diagrammen

  • Angenommen, ich habe einen gewichteten ungerichteten vollständigen Graphen $ G = (V, E) $. Jeder Kante $ e = (u, v, w) $ wird ein positives Gewicht $ w $ zugewiesen. Ich möchte die minimal gewichtete $ (d, h) $ - Baumzerlegung berechnen. Mit $ (d, h) $ - Baumzerlegung meine ich, die Scheitelpunkte $ V $ in $ k $ -Bäume aufzuteilen, so dass die Höhe jedes Baums $ h $ beträgt und jeder Nicht-Blatt-Knoten $ d $ hat Kinder.

    Ich weiß, es ist definitiv $ \ text {NP} $ - Hard, da Minimum $ (1, | V | -1) $ - Tree-Decomposition der minimale Hamiltonpfad ist . Gibt es gute Annäherungsalgorithmen?

    10 May 2012
    Raphael
0 answers