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 গ্রাফ তত্ত্বে গণনামূলক সমস্যা