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

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

Эта концепция была предложена Раджагопаланом и Вазирани. [1] кто использовал его для обеспечения (3/2 + ε) алгоритм аппроксимации для проблемы дерева Штейнера на таких примерах. Впоследствии фактор ε был удален Рицци.[2] и 4/3 алгоритм аппроксимации был получен Chakrabarty et al.[3]Та же концепция использовалась последующими авторами по проблеме дерева Штейнера, например[4] Робинс и Зеликовский[5]предложил алгоритм аппроксимации для проблемы дерева Штейнера, которая на квазидвудольных графах имеет коэффициент аппроксимации 1.28. Сложность алгоритма Робинса и Зеликовского составляет O (мп2), куда м и п - количество терминалов и нетерминалов на графике соответственно. Кроме того, Gröpl et al.[6] дал 1.217-приближенный алгоритм для частного случая равномерно квазидвудольный экземпляры.

Рекомендации

  1. ^ Раджагопалан, Шридхар; Вазирани, Виджай В. (1999), "О релаксации двунаправленного разреза для метрической проблемы дерева Штейнера", Материалы десятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, стр. 742–751.
  2. ^ Рицци, Ромео (2003), "Оценка 3/2 аппроксимации Раджагопалана и Вазирани для итерированной эвристики 1-Штейнера", Инф. Процесс. Lett., 86 (6): 335–338, Дои:10.1016 / S0020-0190 (03) 00210-2.
  3. ^ Чакрабарти, Дипарнаб; Деванур, Нихил Р .; Вазирани, Виджай В. (2008), "Новая геометрия релаксации и алгоритмы для проблемы метрического дерева Штейнера", Proc. 13-я IPCO, Конспект лекций по информатике, 5035, стр. 344–358, Дои:10.1007/978-3-540-68891-4_24, ISBN  978-3-540-68886-0.
  4. ^ Грёпль, Клеменс; Хугарди, Стефан; Нирхофф, Тилль; Prömel, Hans Jürgen (2001), "Нижние границы для алгоритмов приближения для проблемы дерева Штейнера", Теоретико-графические концепции в компьютерных науках: 27-й международный семинар, WG 2001, Конспект лекций по информатике, 2204, Springer-Verlag, Lecture Notes in Computer Science 2204, pp. 217–228, Дои:10.1007/3-540-45477-2_20, ISBN  978-3-540-42707-0.
  5. ^ Робинс, Габриэль; Зеликовский, Александр (2000), "Улучшенное приближение дерева Штейнера в графах", Материалы одиннадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, стр. 770–779.
  6. ^ Грёпль, Клеменс; Хугарди, Стефан; Нирхофф, Тилль; Prömel, Hans Jürgen (2002), "Деревья Штейнера в равномерно квазидвудольных графах", Письма об обработке информации, 83 (4): 195–200, Дои:10.1016 / S0020-0190 (01) 00335-0.