Degree-constrained spanning tree
આલેખ સિદ્ધાંતમાં, ડિગ્રી-મર્યાદિત સ્પૅનિંગ ટ્રી એ એક સ્પૅનિંગ ટ્રી છે જ્યાં મહત્તમ શિરોબિંદુ ડિગ્રી ચોક્કસ અચળાંક k સુધી મર્યાદિત હોય છે. ડિગ્રી-મર્યાદિત સ્પૅનિંગ ટ્રીની સમસ્યા એ નક્કી કરવા માટે છે કે કોઈ ચોક્કસ ગ્રાફમાં ચોક્કસ k માટે આવું સ્પૅનિંગ ટ્રી છે કે કેમ. ઔપચારિક વ્યાખ્યા ઇનપુટઃ n-નોડ દિશાહીન ગ્રાફ G (V, E); હકારાત્મક પૂર્ણાંક k <n. પ્રશ્નઃ શું G પાસે એક સ્પૅનિંગ ટ્રી છે જેમાં કોઈ નોડની ડિગ્રી k કરતા વધારે નથી? એન. પી.-પૂર્ણતા આ સમસ્યા એન. પી.-પૂર્ણ છે. આ હેમિલ્ટોનિયન પાથ સમસ્યામાંથી ઘટાડા દ્વારા દર્શાવી શકાય છે. તે NP-પૂર્ણ રહે છે, ભલે k એ ≤2 મૂલ્ય પર નિશ્ચિત હોય. જો સમસ્યાને ડિગ્રી ≤ k તરીકે વ્યાખ્યાયિત કરવામાં આવે, તો ડિગ્રી-મર્યાદિત સ્પૅનિંગ ટ્રીનો k = 2 કેસ હેમિલ્ટોનિયન પાથ પ્રોબ્લેમ છે. ડિગ્રી-કન્સ્ટ્રેઈન્ડ મિનિમમ સ્પૅનિંગ ટ્રી ભારિત આલેખ પર, ડિગ્રી-કન્સ્ટ્રેઈન્ડ મિનિમમ સ્પૅનિંગ ટ્રી (ડી. સી. એમ. એસ. ટી.) એ ડિગ્રી-કન્સ્ટ્રેઈન્ડ સ્પૅનિંગ ટ્રી છે જેમાં તેની ધારોનો સરવાળો ઓછામાં ઓછો શક્ય સરવાળો ધરાવે છે. ડી. સી. એમ. એસ. ટી. શોધવી એ એન. પી-હાર્ડ સમસ્યા છે. આનુવંશિક અને કીડી આધારિત અલ્ગોરિધમ્સ સહિત બહુપદી સમયમાં સમસ્યાનું સમાધાન કરી શકે તેવા સંશોધનાત્મક અલ્ગોરિધમ્સની દરખાસ્ત કરવામાં આવી છે. એપ્રોક્સીમેશન એલ્ગોરિધમ એક પુનરાવર્તિત બહુપદી સમય અલ્ગોરિધમ આપે છે, જે આલેખ આપવામાં આવે તો, મહત્તમ ડિગ્રી સાથે સ્પૅનિંગ ટ્રી આપે છે, જે તેના કરતા મોટી નથી, જ્યાં તમામ સ્પૅનિંગ ટ્રી પર લઘુત્તમ શક્ય મહત્તમ ડિગ્રી છે. આમ, જો, આવા અલ્ગોરિધમનો કાં તો મહત્તમ ડિગ્રીના સ્પૅનિંગ ટ્રીને પરત કરશે અથવા. સંદર્ભો વૃક્ષમાં ફેલાયેલાં એન. પી.-પૂર્ણ સમસ્યાઓ