Minimalne drzewo rozpinające kosztów trasowania
W informatyce minimalny koszt trasowania drzewa rozpinającego grafu ważonego to drzewo rozpinające minimalizujące sumę odległości parami między wierzchołkami w drzewie. Nazywa się to również drzewem rozpinającym optymalną odległość , drzewem rozpinającym o najkrótszej całkowitej długości ścieżki , drzewem rozpinającym minimalną całkowitą odległość lub drzewem rozpinającym minimalną średnią odległość . Na wykresie nieważonym jest to drzewo rozpinające minimalnego indeksu Wienera . Hu (1974) pisze, że problem konstruowania tych drzew zaproponował Francesco Maffioli.
Skonstruowanie go jest NP-trudne , nawet dla grafów nieważonych. Ma jednak schemat aproksymacji w czasie wielomianowym . Przybliżenie działa poprzez wybranie liczby liczby wierzchołków grafu wejściowego, oraz poprzez przeszukiwanie wszystkich drzew z wewnętrznymi.
Drzewo rozpinające minimalnego kosztu trasowania nieważonego wykresu interwałowego można skonstruować w czasie liniowym. Algorytm czasu wielomianowego jest również znany z wykresów dziedzicznych odległości , ważonych w taki sposób, że ważone odległości są dziedziczne.