Gradbegränsat spännträd

I grafteorin är ett gradbegränsat spannträd ett spännträd där den maximala vertexgraden är begränsad till en viss konstant k . Det gradbegränsade spännträdsproblemet är att bestämma om en viss graf har ett sådant spännträd för ett visst k .

Formell definition

Ingång: n -nod oriktad graf G(V,E); positivt heltal k < n .

Fråga: Har G ett spännträd där ingen nod har en grad större än k ?

NP-fullständighet

Detta problem är NP-komplett ( Garey & Johnson 1979) . Detta kan visas genom en minskning från Hamiltons vägproblem . Det förblir NP-komplett även om k är fixerat till ett värde ≥ 2. Om problemet definieras som att graden måste vara ≤ k , är k = 2-fallet med gradbegränsat spännträd det Hamiltonska vägproblemet.

Gradbegränsat minimumspännande träd

På en viktad graf är ett gradbegränsat minimum spannträd (DCMST) ett gradbegränsat spännträd där summan av dess kanter har minsta möjliga summa. Att hitta en DCMST är ett NP-Hard problem.

Heuristiska algoritmer som kan lösa problemet i polynomtid har föreslagits, inklusive genetiska och myrbaserade algoritmer.

Approximationsalgoritm

Fürer & Raghavachari (1994) ger en iterativ polynomtidsalgoritm som, givet en graf $G$ , returnerar ett spännträd med maximal grad som inte är större än $\Delta ^{*}+1$ , där $\Delta ^{*}$ är den minsta möjliga maximala graden över alla spännande träd. Således, om $k=\Delta ^{*}$ , kommer en sådan algoritm antingen att returnera ett spännträd med maximal grad $k$ eller $k+1$ .

•   Garey, Michael R .; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , WH Freeman, ISBN 978-0-7167-1045-5 . A2.1: ND1, sid. 206. {{ citation }} : CS1 underhåll: postscript ( länk )
•   Fürer, Martin; Raghavachari, Balaji (1994), "Approximating the minimum-degree Steiner tree to within one of optimal", Journal of Algorithms , 17 (3): 409–423, CiteSeerX 10.1.1.136.1089 , doi : 10.1006/2.94.1.1.1 .