Drzewo rozpinające o minimalnym stopniu

W teorii grafów drzewo rozpinające o minimalnym stopniu jest podzbiorem krawędzi grafu połączonego , który łączy ze sobą wszystkie wierzchołki bez żadnych cykli , a jego maksymalny stopień wierzchołków jest jak najmniejszy. Oznacza to, że jest to drzewo rozpinające , którego maksymalny stopień jest minimalny.

Problem decyzyjny jest następujący: mając dany graf G i liczbę całkowitą k , czy G ma takie drzewo rozpinające, że żaden wierzchołek nie ma stopnia większego niż k ? Jest to również znane jako drzewa rozpinającego o ograniczonym stopniu .

Algorytmy

Znalezienie drzewa rozpinającego o minimalnym stopniu grafu nieskierowanego jest NP-trudne . Można to pokazać poprzez redukcję do problemu ścieżki Hamiltona . W przypadku grafów skierowanych znalezienie drzewa rozpinającego o minimalnym stopniu jest również NP-trudne.

R. Krishman i B. Raghavachari (2001) mają quasi-wielomianowy algorytm aproksymacji czasu do rozwiązania problemu dla grafów skierowanych.

M. Haque, Md. R. Uddin i Md. A. Kashem (2007) znaleźli liniowy algorytm czasu, który może znaleźć drzewo rozpinające o minimalnym stopniu grafów szeregowo-równoległych o małych stopniach.

G. Yao, D. Zhu, H. Li i S. Ma (2008) znaleźli algorytm czasu wielomianowego , który może znaleźć drzewo rozpinające minimalnego stopnia skierowanych grafów acyklicznych .