Квазидвудольным называется случай задачи Штейнера о минимальном дереве (состоящей из неориентированного графа G и множества R терминальных вершин), в котором нетерминальные вершины графа G образуют независимое множество. Это определение обобщает концепцию двудольного графа — если граф G двудолен и одна из его долей образует множество R, то множество R автоматически является независимым.
Данную концепцию предложили Раджагопалан и Вазирани и использовали её, чтобы дать -аппроксимационный алгоритм для задачи Штейнера в таких графах. Впоследствии Рицци избавился от в данной оценке, а Чакрабарти с соавторами предложили 4/3-аппроксимационный алгоритм. В дальнейшем ту же концепцию использовали другие авторы, например Робинс и Зеликовский предложили аппроксимационный алгоритм для задачи Штейнера, который на квазидвудольных графах имеет аппроксимационный коэффициент 1,28. Алгоритм Робинса и Зеликовского работает за время , где m и n — количества терминальных и нетерминальных вершин в графе соответственно. В дальнейшем, Грёпль с соавторами предложили 1,217-аппроксимационный алгоритм для особого случая однородных квазидвудольных случаев.
Примечания
Литература
Категория:Семейства графов Категория:Двудольные графы