Квазидвудольный граф
В математической области теории графов экземпляр задачи о дереве Штейнера (состоящий из неориентированного графа G и множества R терминальных вершин, которые должны быть связаны друг с другом) называется квазидвудольным, если нетерминальные вершины в G образуют независимое множество , т.е. если каждое ребро инцидентно хотя бы одному терминалу. Это обобщает концепцию двудольного графа : если G двудольный, а R — множество вершин на одной стороне двудольного графа, то множество R автоматически независимо.
Эту концепцию представили Раджагопалан и Вазирани. [1] (3/2 + ε) который использовал его для создания алгоритма аппроксимации для задачи дерева Штейнера в таких случаях. Впоследствии фактор ε был удален Рицци. [2] 4/3 а алгоритм аппроксимации был получен Чакрабарти и др. [3] Та же концепция использовалась последующими авторами при решении проблемы дерева Штейнера, например [4] Робинс и Зеликовский [5] предложил алгоритм аппроксимации задачи дерева Штейнера, который на квазидвудольных графах имеет коэффициент аппроксимации 1,28. Сложность алгоритма Робинса и Зеликовского составляет O( m n 2 ) , где m и n — количество терминалов и нетерминалов в графе соответственно. В 2012 году Гоеманс и др. [6] дал алгоритм аппроксимации 73/60 ≈ 1,217 для задачи дерева Штейнера на квазидвудольных графах; алгоритм, достигающий того же коэффициента аппроксимации, был ранее известен для частного случая квазидвудольных графов с ребрами единичной стоимости. [7]
Ссылки
[ редактировать ]- ^ Раджагопалан, Шридхар; Вазирани, Виджай В. (1999), «О релаксации двунаправленного разреза для метрической проблемы дерева Штейнера», Труды десятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 742–751 .
- ^ Рицци, Ромео (2003), «О приближении 3/2 Раджагопалана и Вазирани, связанном с итерированной эвристикой 1-Штайнера», Inf. Процесс. Летт. , 86 (6): 335–338, doi : 10.1016/S0020-0190(03)00210-2 .
- ^ Чакрабарти, Дипарнаб; Деванур, Нихил Р.; Вазирани, Виджай В. (2008), «Новые релаксации и алгоритмы, основанные на геометрии, для задачи метрического дерева Штейнера», Proc. 13-я IPCO , Конспекты лекций по информатике , вып. 5035, стр. 344–358, номер документа : 10.1007/978-3-540-68891-4_24 , ISBN. 978-3-540-68886-0 .
- ^ Грепль, Клеменс; Хугарди, Стефан; Нирхофф, Тилль; Премель, Ханс Юрген (2001), «Нижние границы алгоритмов аппроксимации для задачи дерева Штейнера», Теоретико-графовые концепции в информатике: 27-й международный семинар, WG 2001 , Конспекты лекций по информатике, том. 2204, Springer-Verlag, Конспекты лекций по информатике 2204, стр. 217–228, doi : 10.1007/3-540-45477-2_20 , ISBN 978-3-540-42707-0 .
- ^ Робинс, Габриэль; Зеликовский, Александр (2000), «Улучшенная аппроксимация дерева Штейнера в графах», Труды одиннадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 770–779 .
- ^ Гоеманс, Мишель; Олвер, Нил; Ротвосс, Томас; Зенклюсен, Рико (2012). «Матроиды и пробелы в целостности для гиперграфических релаксаций дерева Штейнера» . Материалы сорок четвертого ежегодного симпозиума ACM по теории вычислений . п. 1161-1176. дои : 10.1145/2213977.2214081 . ISBN 9781450312455 . S2CID 13424446 .
- ^ Грепль, Клеменс; Хугарди, Стефан; Нирхофф, Тилль; Премель, Ханс Юрген (2002), «Деревья Штейнера в равномерно квазидвудольных графах», Information Processing Letters , 83 (4): 195–200, doi : 10.1016/S0020-0190(01)00335-0 .