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