MaxDDBS - MaxDDBS

Bu maqola ko'proq kerak boshqa maqolalarga havolalar yordamlashmoq uni ensiklopediyaga qo'shib qo'ying. Iltimos yordam bering ushbu maqolani yaxshilang havolalarni qo'shish orqali kontekst bilan bog'liq bo'lgan mavjud matn ichida. (2019 yil yanvar) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)

The Maksimal daraja va diametr bilan chegaralangan subgraf muammosi (MaxDDBS) muammo grafik nazariyasi.

Bog'langan holda berilgan asosiy grafik G, daraja uchun yuqori chegara dva diametri uchun yuqori chegara k, biz eng katta subgrafani qidiramiz S ning G maksimal daraja bilan d va diametri ko'pi bilan k. Ushbu muammoni daraja-diametrli subgraf muammosi deb ham atashadi, chunki u quyidagilarni o'z ichiga oladi daraja diametri muammosi maxsus holat sifatida (ya'ni, asosiy grafik sifatida etarlicha katta to'liq grafikani olish orqali). Daraja-Diametri muammosini tabiiy ravishda umumlashtirishiga qaramay, MaxDDBS faqat 2011 yilda o'rganila boshlandi, Daraja-Diametri muammosi bo'yicha tadqiqotlar 1960-yillardan beri faol bo'lib kelmoqda. Hisoblashning murakkabligi bilan bog'liq holda, muammo APXda emas, balki NP-qattiqdir (ya'ni uni polinom vaqtidagi doimiy koeffitsientga yaqinlashtirish mumkin emas).

Adabiyotlar

1. Combinatorics Wiki-dagi MaxDDBS sahifasi
2. A.Dekker, X.Perez-Rozz, G.Pineda-Vilyavisensio va P.Voters. Maksimal daraja va diametrga asoslangan subgraf va uning qo'llanilishi. Matematik modellashtirish va algoritmlar jurnali, 2012. DOI: 10.1007 / s10852-012-9182-8
3. M.Miller, H.Perez-Rozes va J.Ryan. Meshdagi maksimal daraja va diametr bilan chegaralangan subgraf. Diskret amaliy matematika, 2012. DOI: 10.1016 / j.dam.2012.03.035