Минимальная стоимость маршрутизации связующего дерева

В информатике взвешенного остовное дерево с минимальной стоимостью маршрутизации графа — это остовное дерево, минимизирующее сумму попарных расстояний между вершинами в дереве. Его также называют связующим деревом оптимального расстояния , связующим деревом кратчайшего общего пути , связующим деревом минимального общего расстояния или связующим деревом минимального среднего расстояния . В невзвешенном графе это остовное дерево минимального индекса Винера . ^[1]Ху (1974) пишет, что задачу построения этих деревьев предложил Франческо Маффиоли. ^[2]

Его NP-трудно построить даже для невзвешенных графов. ^[3]^[4] Однако он имеет схему аппроксимации с полиномиальным временем . Аппроксимация работает путем выбора числа $k$ это зависит от коэффициента аппроксимации, а не от количества вершин входного графа, а также от поиска среди всех деревьев с $k$ внутренние узлы. ^[5]

Охватывающее дерево минимальной стоимости маршрутизации невзвешенного интервального графа может быть построено за линейное время. ^[6] Алгоритм с полиномиальным временем также известен для дистанционно-наследственных графов , взвешенных так, что взвешенные расстояния являются наследственными. ^[7]

Соображения справедливости

В нескольких работах предполагается, что разные люди могут иметь разные предпочтения в отношении ребер графа, и цель состоит в том, чтобы найти лучшее «социально» остовное дерево.

Дарманн, Кламлер и Пферши представляют жадный алгоритм , который находит такое остовное дерево. ^[8]

Эскофье, Гурвес и Монно изучают проблему в рамках эгалитарного правила – максимизации наименьшей полезности агента. ^[9]
Галанд, Перни и Спаньяард исследуют проблему по критерию минимизации интеграла Шоке . ^[10]

См. также

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

Ссылки

^ Добрынин Андрей А.; Энтрингер, Роджер; Гутман, Иван (2001). «Индекс Винера деревьев: теория и приложения». Acta Applicandae Mathematicae . 66 (3): 211–249. дои : 10.1023/А:1010767517079 .
^ Ху, TC (сентябрь 1974 г.). «Оптимальные связующие деревья связи». SIAM Journal по вычислительной технике . 3 (3): 188–195. дои : 10.1137/0203015 . МР 0427116 .
^ Джонсон, Д.С.; Ленстра, Дж. К.; Кан, AHG Ринной (декабрь 1978 г.). «Сложность проблемы проектирования сети» (PDF) . Сети . 8 (4): 279–285. дои : 10.1002/net.3230080402 .
^ Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Фримен. A2.1: ND3, стр. 206. ИСБН 978-0-7167-1044-8 .
^ Ву, Бан Е; Лансия, Джузеппе; Бафна, Винет; Чао, Кун-Мао; Рави, Р.; Тан, Чуан И (январь 2000 г.). «Схема аппроксимации полиномиального времени для остовных деревьев с минимальной стоимостью маршрутизации». SIAM Journal по вычислительной технике . 29 (3): 761–778. дои : 10.1137/S009753979732253X . S2CID 1639329 .
^ Дальхаус, Элиас; Данкельманн, Питер; Рави, Р. (2004). «Алгоритм линейного времени для вычисления MAD-дерева интервального графа». Письма об обработке информации . 89 (5): 255–259. дои : 10.1016/j.ipl.2003.11.009 . МР 2032568 .
^ Дальхаус, Э.; Данкельманн, П.; Годдард, В.; Сварт, ХК (сентябрь 2003 г.). «MAD-деревья и дистанционно-наследственные графы». Дискретная прикладная математика . 131 (1): 151–167. дои : 10.1016/S0166-218X(02)00422-5 .
^ Дарманн, Андреас; Кламлер, Кристиан; Пферши, Ульрих (апрель 2011 г.). «Поиск лучших с точки зрения общества связующих деревьев». Теория и решение . 70 (4): 511–527. дои : 10.1007/s11238-010-9228-1 .
^ Эскофье, Бруно; Гурвес, Лоран; Монно, Жером (март 2013 г.). «Честные решения некоторых задач многоагентной оптимизации». Автономные агенты и мультиагентные системы . 26 (2): 184–201. дои : 10.1007/s10458-011-9188-z .
^ Галанд, Люси; Перни, Патрис; Спанджаард, Оливье (июль 2010 г.). «Оптимизация на основе Шоке в многокритериальных задачах кратчайшего пути и связующего дерева» (PDF) . Европейский журнал операционных исследований . 204 (2): 303–315. дои : 10.1016/j.ejor.2009.10.015 .

Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее .

[deg-1] Добрынин Андрей А.; Энтрингер, Роджер; Гутман, Иван (2001). «Индекс Винера деревьев: теория и приложения». Acta Applicandae Mathematicae . 66 (3): 211–249. дои : 10.1023/А:1010767517079 .

[hu-2] Ху, TC (сентябрь 1974 г.). «Оптимальные связующие деревья связи». SIAM Journal по вычислительной технике . 3 (3): 188–195. дои : 10.1137/0203015 . МР 0427116 .

[jlr-3] Джонсон, Д.С.; Ленстра, Дж. К.; Кан, AHG Ринной (декабрь 1978 г.). «Сложность проблемы проектирования сети» (PDF) . Сети . 8 (4): 279–285. дои : 10.1002/net.3230080402 .

[gj-4] Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Фримен. A2.1: ND3, стр. 206. ИСБН 978-0-7167-1044-8 .

[wlbcrt-5] Ву, Бан Е; Лансия, Джузеппе; Бафна, Винет; Чао, Кун-Мао; Рави, Р.; Тан, Чуан И (январь 2000 г.). «Схема аппроксимации полиномиального времени для остовных деревьев с минимальной стоимостью маршрутизации». SIAM Journal по вычислительной технике . 29 (3): 761–778. дои : 10.1137/S009753979732253X . S2CID 1639329 .

[ddr-6] Дальхаус, Элиас; Данкельманн, Питер; Рави, Р. (2004). «Алгоритм линейного времени для вычисления MAD-дерева интервального графа». Письма об обработке информации . 89 (5): 255–259. дои : 10.1016/j.ipl.2003.11.009 . МР 2032568 .

[ddgs-7] Дальхаус, Э.; Данкельманн, П.; Годдард, В.; Сварт, ХК (сентябрь 2003 г.). «MAD-деревья и дистанционно-наследственные графы». Дискретная прикладная математика . 131 (1): 151–167. дои : 10.1016/S0166-218X(02)00422-5 .

[8] Дарманн, Андреас; Кламлер, Кристиан; Пферши, Ульрих (апрель 2011 г.). «Поиск лучших с точки зрения общества связующих деревьев». Теория и решение . 70 (4): 511–527. дои : 10.1007/s11238-010-9228-1 .

[9] Эскофье, Бруно; Гурвес, Лоран; Монно, Жером (март 2013 г.). «Честные решения некоторых задач многоагентной оптимизации». Автономные агенты и мультиагентные системы . 26 (2): 184–201. дои : 10.1007/s10458-011-9188-z .

[10] Галанд, Люси; Перни, Патрис; Спанджаард, Оливье (июль 2010 г.). «Оптимизация на основе Шоке в многокритериальных задачах кратчайшего пути и связующего дерева» (PDF) . Европейский журнал операционных исследований . 204 (2): 303–315. дои : 10.1016/j.ejor.2009.10.015 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]