Охватывающее дерево минимальной степени

В теории графов остовное дерево минимальной степени — это подмножество ребер связного графа, которое соединяет все вершины вместе без каких-либо циклов , а максимальная степень его вершин как можно меньше. То есть это остовное дерево , максимальная степень которого минимальна.

Проблема решения такова: для данного графа G и целого числа k существует ли в G остовное дерево такое, что ни одна вершина не имеет степени выше k ? Это также известно как проблема связующего дерева с ограничением по степени .

Алгоритмы

Найти остовное дерево минимальной степени неориентированного графа NP-трудно . Это можно показать путем сведения к гамильтоновой задаче о пути . Для ориентированных графов нахождение остовного дерева минимальной степени также является NP-трудным. ^[1]

Р. Кришман и Б. Рагхавачари (2001) разработали алгоритм аппроксимации квазиполиномиального времени для решения проблемы ориентированных графов. ^[1]

М. Хак, доктор Р. Уддин и доктор медицины А. Кашем (2007) нашли алгоритм с линейным временем , который может найти остовное дерево минимальной степени последовательно-параллельных графов с малыми степенями. ^[2]

Г. Яо, Д. Чжу, Х. Ли и С. Ма (2008) нашли алгоритм с полиномиальным временем , который может найти остовное дерево минимальной степени ориентированных ациклических графов . ^[3]

Ссылки

^ Jump up to: ^а ^б Кришнан, Радха; Рагхавачари, Баладжи (2001). «Задача направленного остовного дерева минимальной степени» . ФСТ ТКС 2001: Основы программных технологий и теоретической информатики . Конспекты лекций по информатике. Том. 2245. стр. 232–243. дои : 10.1007/3-540-45294-X_20 . ISBN 978-3-540-43002-5 .
^ Хак, Мохаммед Атикул; Уддин, штат Мэриленд Реаз; Кашем, штат Мэриленд Абул (2007). «Алгоритм нахождения остовного дерева минимальной степени последовательно-параллельных графов» . 2007 Международная конференция по информационным и коммуникационным технологиям . стр. 27–31. дои : 10.1109/ICICT.2007.375336 . ISBN 978-984-32-3394-3 . S2CID 17947444 .
^ Яо, Гохуэй; Чжу, Дамин; Ли, Хэнву; Ма, Шаохан (6 сентября 2008 г.). «Полиномиальный алгоритм для вычисления остовных деревьев минимальной степени ориентированных ациклических графов с применением к задаче широковещания». Дискретная математика . 308 (17): 3951–3959. дои : 10.1016/j.disc.2007.07.105 .

[kr-1] Jump up to: ^а ^б Кришнан, Радха; Рагхавачари, Баладжи (2001). «Задача направленного остовного дерева минимальной степени» . ФСТ ТКС 2001: Основы программных технологий и теоретической информатики . Конспекты лекций по информатике. Том. 2245. стр. 232–243. дои : 10.1007/3-540-45294-X_20 . ISBN 978-3-540-43002-5 .

[2] Хак, Мохаммед Атикул; Уддин, штат Мэриленд Реаз; Кашем, штат Мэриленд Абул (2007). «Алгоритм нахождения остовного дерева минимальной степени последовательно-параллельных графов» . 2007 Международная конференция по информационным и коммуникационным технологиям . стр. 27–31. дои : 10.1109/ICICT.2007.375336 . ISBN 978-984-32-3394-3 . S2CID 17947444 .

[3] Яо, Гохуэй; Чжу, Дамин; Ли, Хэнву; Ма, Шаохан (6 сентября 2008 г.). «Полиномиальный алгоритм для вычисления остовных деревьев минимальной степени ориентированных ациклических графов с применением к задаче широковещания». Дискретная математика . 308 (17): 3951–3959. дои : 10.1016/j.disc.2007.07.105 .

[1]

[2]

[3]