MaxDDBS - MaxDDBS

В Задача о подграфе, ограниченном максимальной степенью и диаметром (MaxDDBS) проблема в теория графов.

Учитывая подключенный граф хоста G, верхняя оценка степени d, и оценка сверху диаметра k, ищем самый большой подграф S из грамм с максимальной степенью не более d и диаметр не более k. Эта проблема также называется проблемой подграфа степени-диаметра, поскольку она содержит проблема диаметра градусов как частный случай (а именно, взяв достаточно большой полный граф в качестве основного графа). Несмотря на то, что MaxDDBS является естественным обобщением задачи о градусах диаметра, исследование MaxDDBS началось только в 2011 году, в то время как исследования по проблеме градуса диаметра ведутся с 1960-х годов. Что касается вычислительной сложности, проблема NP-сложна и не в APX (т.е. ее нельзя аппроксимировать с точностью до постоянного множителя за полиномиальное время).

Рекомендации

1. Страница MaxDDBS в Combinatorics Wiki
2. А. Деккер, Х. Перес-Росес, Дж. Пинеда-Вильявисенсио и П. Уоттерс. Подграф, ограниченный максимальной степенью и диаметром, и его приложения. Журнал математического моделирования и алгоритмов, 2012. DOI: 10.1007 / s10852-012-9182-8
3. М. Миллер, Х. Перес-Розес и Дж. Райан. Подграф, ограниченный максимальной степенью и диаметром в сетке. Дискретная прикладная математика, 2012. DOI: 10.1016 / j.dam.2012.03.035