MaxDDBS
મહત્તમ ડિગ્રી-એન્ડ-ડાયમીટર-બાઉન્ડેડ સબગ્રાફ પ્રોબ્લેમ (એમ. એસ. ડી. ડી. બી. એસ.) આલેખ સિદ્ધાંતમાં એક સમસ્યા છે. જોડાયેલા યજમાન આલેખ G ને જોતાં, ડિગ્રી d માટે ઉપલી બાઉન્ડ અને વ્યાસ k માટે ઉપલી બાઉન્ડ, આપણે G નો સૌથી મોટો સબગ્રાફ S શોધીએ છીએ જેનો મહત્તમ ડિગ્રી d અને મહત્તમ વ્યાસ k હોય છે. આ સમસ્યાને ડિગ્રી-વ્યાસ સબગ્રાફ સમસ્યા તરીકે પણ ઓળખવામાં આવે છે, કારણ કે તેમાં ડિગ્રી વ્યાસની સમસ્યા એક ખાસ કેસ તરીકે હોય છે (એટલે કે, યજમાન આલેખ તરીકે પૂરતા પ્રમાણમાં મોટા સંપૂર્ણ ગ્રાફને લઈને). ડિગ્રી-વ્યાસ સમસ્યાનું કુદરતી સામાન્યીકરણ હોવા છતાં, મેક્સડીડીબીએસની તપાસ માત્ર 2011 માં શરૂ થઈ હતી, જ્યારે ડિગ્રી-વ્યાસ સમસ્યામાં સંશોધન 1960 ના દાયકાથી સક્રિય છે. તેની કોમ્પ્યુટેશનલ જટિલતાને ધ્યાનમાં રાખીને, સમસ્યા એન. પી.-હાર્ડ છે, અને એ. પી. એક્સ. માં નહીં (એટલે કે. બહુપદી સમયમાં અચળ પરિબળની અંદર તેનો અંદાજ લગાવી શકાતો નથી). સંદર્ભો કોમ્બિનેટોરિક્સ વિકી 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 આલેખ સિદ્ધાંતમાં કોમ્પ્યુટેશનલ સમસ્યાઓ