Квазидвудольный граф

Квазидвудольным называется случай задачи Штейнера о минимальном дереве (состоящей из неориентированного графа 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-аппроксимационный алгоритм для особого случая однородных квазидвудольных случаев.

Примечания

1. Rajagopalan, Vazirani, 1999, с. 742–751.
2. Rizzi, 2003, с. 335–338.
3. Chakrabarty, Devanur, Vazirani, 2008, с. 344–358.
4. Gröpl, Hougardy, Nierhoff, Prömel, 2001, с. 217–228.
5. Robins, Zelikovsky, 2000, с. 770–779.
6. Gröpl, Hougardy, Nierhoff, Prömel, 2002, с. 195–200.

Литература

• Clemens Gröpl, Stefan Hougardy, Till Nierhoff, Hans Jürgen Prömel. 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.
• Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani. New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem // Proc. 13th IPCO. — 2008. — Т. 5035. — С. 344–358. — (Lecture Notes in Computer Science). — ISBN 978-3-540-68886-0. — doi:10.1007/978-3-540-68891-4_24.
• Clemens Gröpl, Stefan Hougardy, Till Nierhoff, Hans Jürgen Prömel. Lower Bounds for Approximation Algorithms for the Steiner Tree Problem // Graph-Theoretic Concepts in Computer Science : 27th International Workshop, WG 2001. — Springer-Verlag, 2001. — Т. 2204. — С. 217–228. — (Lecture Notes in Computer Science). — ISBN 978-3-540-42707-0. — doi:10.1007/3-540-45477-2_20.
• Gabriel Robins, Alexander Zelikovsky. Improved Steiner tree approximation in graphs // Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms. — 2000. — С. 770–779.