|
Труды Института математики, 2019, том 27, номер 1-2, страницы 53–59
(Mi timb303)
|
|
|
|
Решение задачи о взвешенной независимой $\{K_1,K_2\}$-упаковке древесных кографов
В. В. Лепин Институт математики НАН Беларуси
Аннотация:
Пусть $\mathcal{H}$ — фиксированное множество связных графов. $\mathcal{H}$-упаковкой графа $G$ называется множество $\mathcal{S}=\{G_1,G_2,\ldots,G_m\}$ попарно не пересекающихся подграфов графа $G,$ каждый из которых изоморфен графу из $\mathcal{H}.$ Независимой $\mathcal{H}$-упаковкой графа $G$ называется $\mathcal{H}$-упаковка $S,$ в которой никакие два подграфа упаковки не соединены ребром графа $G.$ Если дан граф $G$ с весовыми функциями $\omega_V:~V(G)\to\mathbb{N}$ и $\omega_E:~E(G)\to\mathbb{N}$ на вершинах и ребрах и независимая $\{K_1,K_2\}$-упаковка $S$ графа $G,$ то весом $S$ называется $\sum_{v\in U}\omega_V(v)+\sum_{e\in F}\omega_E(e),$ где $U=\bigcup_{G_i\in\mathcal{S},~G_i\cong K_1}V(G_i)$ и $F=\bigcup_{G_i\in\mathcal{S}}E(G_i).$ Рассматривается задача нахождения независимой $\{K_1,K_2\}$-упаковки наибольшего веса.
Представлен алгоритм, который решает задачу о взвешенной независимой $\{K_1,K_2\}$-упаковке графа в классе древесных кографов. Временная сложность алгоритма $O(m),$ где $m=|E(G)|.$
Поступила в редакцию: 30.10.2018
Образец цитирования:
В. В. Лепин, “Решение задачи о взвешенной независимой $\{K_1,K_2\}$-упаковке древесных кографов”, Тр. Ин-та матем., 27:1-2 (2019), 53–59
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/timb303 https://www.mathnet.ru/rus/timb/v27/i1/p53
|
Статистика просмотров: |
Страница аннотации: | 56 | PDF полного текста: | 30 | Список литературы: | 17 |
|