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 گراف تھیوری میں کمپیوٹیشنل مسائل