MaxDDBS
அதிகபட்ச டிகிரி மற்றும் விட்டம் வரம்புக்குட்பட்ட சப் கிராஃப் சிக்கல் (மேக்ஸ். டி. டி. பி. எஸ்) என்பது வரைபடக் கோட்பாட்டில் ஒரு சிக்கலாகும். ஒரு இணைக்கப்பட்ட புரவலன் வரைபடம் G ஐப் பொறுத்தவரை, டிகிரி d க்கு மேல் வரம்பும், விட்டம் k க்கு மேல் வரம்பும், G இன் மிகப்பெரிய துணை வரைபடம் S ஐ அதிகபட்ச டிகிரி d மற்றும் அதிகபட்ச விட்டம் k உடன் பார்க்கிறோம். இந்த சிக்கல் டிகிரி-விட்டம் துணை வரைபட சிக்கல் என்றும் குறிப்பிடப்படுகிறது, ஏனெனில் இது ஒரு சிறப்பு நிகழ்வாக டிகிரி விட்டம் சிக்கலைக் கொண்டுள்ளது (அதாவது, ஒரு புரவலன் வரைபடமாக போதுமான பெரிய முழுமையான வரைபடத்தை எடுத்துக்கொள்வதன் மூலம்). டிகிரி-விட்டம் சிக்கலின் இயற்கையான பொதுமைப்படுத்தலாக இருந்தபோதிலும், மேக்ஸ். டி. டி. பி. எஸ் 2011 இல் மட்டுமே ஆராயத் தொடங்கியது, அதே நேரத்தில் டிகிரி-விட்டம் சிக்கலில் ஆராய்ச்சி 1960 களில் இருந்து செயலில் உள்ளது. அதன் கணக்கீட்டு சிக்கலைப் பொறுத்தவரை, சிக்கல் NP-கடினமானது, மற்றும் APX இல் இல்லை (அதாவது. பல்லுறுப்புக்கோவை நேரத்தில் ஒரு நிலையான காரணிக்குள் இதை தோராயமாக மதிப்பிட முடியாது). குறிப்புகள் விக்கி காம்பினடோரிக்ஸ் இல் உள்ள MaxDDBS பக்கம் A.Dekker, H.Perez-Roses, G.Pineda-Villavicencio, மற்றும் P.Watters. அதிகபட்ச பட்டம் மற்றும் விட்டம்-வரம்புக்குட்பட்ட துணை வரைபடம் மற்றும் அதன் பயன்பாடுகள். கணித மாதிரி மற்றும் வழிமுறைகளின் இதழ், 2012. டிஓஐஃ 10.1007/s10852-012-9182-8 M.Miller, H.Perez-Roses, மற்றும் J.Ryan. மெஷில் அதிகபட்ச டிகிரி மற்றும் விட்டம் வரம்புக்குட்பட்ட துணை வரைபடம். டிஸ்கிரீட் அப்ளைடு மேத்தமேட்டிக்ஸ், 2012. டிஓஐஃ 10.1016/j.dam.2012.03.035 வரைபடக் கோட்பாட்டில் கணக்கீட்டு சிக்கல்கள்