Minsta gradspännande träd

I grafteorin är ett minimigradspännande träd en delmängd av kanterna på en ansluten graf som förbinder alla hörn tillsammans, utan några cykler , och dess maximala grad av dess hörn så liten som möjligt. Det vill säga, det är ett spännträd vars maximala grad är minimal.

Beslutsproblemet är: Givet en graf G och ett heltal k , har G ett spännträd så att ingen vertex har en grad större än k ? Detta är också känt som problemet med gradbegränsade spannträd .

Algoritmer

Att hitta det minsta gradenspännande trädet för en oriktad graf är NP-hårt . Detta kan visas genom att reducera till Hamiltons vägproblem . För riktade grafer är det också NP-svårt att hitta det minsta gradenspännande trädet.

R. Krishman och B. Raghavachari (2001) har en kvasipolynomisk tidsapproximationsalgoritm för att lösa problemet för riktade grafer.

M. Haque, Md. R. Uddin och Md. A. Kashem (2007) hittade en linjär tidsalgoritm som kan hitta det minsta gradöverskridande trädet för serieparallella grafer med små grader.

G. Yao, D. Zhu, H. Li och S. Ma (2008) hittade en polynomisk tidsalgoritm som kan hitta det minsta gradenspännande trädet för riktade acykliska grafer .