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। डी. ओ. आई.: ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं