Квазидвудольный граф (Tfg[n;fr;kl,udw ijgs)

Квазидвудольным называется случай задачи Штейнера о минимальном дереве (состоящей из неориентированного графа G и множества R терминальных вершин), в котором нетерминальные вершины графа G образуют независимое множество. Это определение обобщает концепцию двудольного графа — если граф G двудолен и одна из его долей образует множество R, то множество R автоматически является независимым.

Данную концепцию предложили Раджагопалан и Вазирани^[1] и использовали её, чтобы дать $(3/2+\epsilon )$ -аппроксимационный алгоритм для задачи Штейнера в таких графах. Впоследствии Рицци избавился от $\epsilon$ в данной оценке^[2], а Чакрабарти с соавторами предложили 4/3-аппроксимационный алгоритм^[3]. В дальнейшем ту же концепцию использовали другие авторы, например^[4] Робинс и Зеликовский^[5] предложили аппроксимационный алгоритм для задачи Штейнера, который на квазидвудольных графах имеет аппроксимационный коэффициент 1,28. Алгоритм Робинса и Зеликовского работает за время $O(mn^{2})$ , где m и n — количества терминальных и нетерминальных вершин в графе соответственно. В дальнейшем, Грёпль с соавторами^[6] предложили 1,217-аппроксимационный алгоритм для особого случая однородных квазидвудольных случаев.

Примечания

↑ Rajagopalan, Vazirani, 1999, с. 742–751.
↑ Rizzi, 2003, с. 335–338.
↑ Chakrabarty, Devanur, Vazirani, 2008, с. 344–358.
↑ Gröpl, Hougardy, Nierhoff, Prömel, 2001, с. 217–228.
↑ Robins, Zelikovsky, 2000, с. 770–779.
↑ 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.

[_1b68338892ff8d76-1] Rajagopalan, Vazirani, 1999, с. 742–751.

[_73b7261e5aaff5f8-2] Rizzi, 2003, с. 335–338.

[_26461e316bb90ab8-3] Chakrabarty, Devanur, Vazirani, 2008, с. 344–358.

[_483db6f9404b1fda-4] Gröpl, Hougardy, Nierhoff, Prömel, 2001, с. 217–228.

[_f47e3395a110f939-5] Robins, Zelikovsky, 2000, с. 770–779.

[_a2e26818f67a1678-6] Gröpl, Hougardy, Nierhoff, Prömel, 2002, с. 195–200.

[1]

[2]

[3]

[4]

[5]

[6]