Меню Главная Случайная статья Настройки Квазидвудольный граф Материал из https://ru.wikipedia.org Квазидвудольным называется случай задачи Штейнера о минимальном дереве (состоящей из неориентированного графа G и множества R терминальных вершин), в котором нетерминальные вершины графа G образуют независимое множество. Это определение обобщает концепцию двудольного графа — если граф G двудолен и одна из его долей образует множество R, то множество R автоматически является независимым. Данную концепцию предложили Раджагопалан и Вазирани[1] и использовали её, чтобы дать ${\displaystyle (3/2+\epsilon )}$-аппроксимационный алгоритм для задачи Штейнера в таких графах. Впоследствии Рицци избавился от ${\displaystyle \epsilon }$ в данной оценке[2], а Чакрабарти с соавторами предложили 4/3-аппроксимационный алгоритм[3]. В дальнейшем ту же концепцию использовали другие авторы, например[4] Робинс и Зеликовский[5] предложили аппроксимационный алгоритм для задачи Штейнера, который на квазидвудольных графах имеет аппроксимационный коэффициент 1,28. Алгоритм Робинса и Зеликовского работает за время ${\displaystyle O(mn^{2})}$, где m и n — количества терминальных и нетерминальных вершин в графе соответственно. В дальнейшем, Грёпль с соавторами[6] предложили 1,217-аппроксимационный алгоритм для особого случая однородных квазидвудольных случаев. Примечания Rajagopalan, Vazirani, 1999, с. 742–751. Rizzi, 2003, с. 335–338. Chakrabarty, Devanur, Vazirani, 2008, с. 344–358. Grpl, Hougardy, Nierhoff, Prmel, 2001, с. 217–228. Robins, Zelikovsky, 2000, с. 770–779. Grpl, Hougardy, Nierhoff, Prmel, 2002, с. 195–200. Литература Clemens Grpl, Stefan Hougardy, Till Nierhoff, Hans Jrgen Prmel. Steiner trees in uniformly quasi-bipartite graphs // Information Processing Letters. — 2002. — Т. 83, вып. 4. — С. 195–200. — doi:10.1016/S0020-0190(01)00335-0. Sridhar Rajagopalan, Vijay V. Vazirani. On the bidirected cut relaxation for the metric Steiner tree problem // Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms. — 1999. — С. 742–751. Romeo Rizzi. On Rajagopalan and Vazirani's 3/2-approximation bound for the Iterated 1-Steiner heuristic // Inf. Process. Lett.. — 2003. — Т. 86, вып. 6. — С. 335–338. — doi:10.1016/S0020-0190(03)00210-2.