Том 4, серия 1, номер 3, 1997 г., Стр. 3-8

УДК 519.17
А. А. Агеев
Сложность нахождения максимального взвешенного джойна в графе

Аннотация:
Подмножество ребер $J\subseteq E(G)$ в неориентированном графе $G$ называют джойном, если не более половины ребер каждого цикла графа $G$ содержится в $J$. Рассмотрена задача нахождения джойна максимального веса: при заданных графе $G$ и реберном взвешивании $c:E(G)\to\mathbf R$ найти джойн максимального веса. Показано, что данная задача является NP-трудной в случае произвольных графов и 0,1-весов. Установлено также, что в случае последовательно-параллельных графов и произвольных весов рассматриваемая задача может быть решена за время $O(n^3)$, где $n$ –число вершин в графе.
Библиогр. 7.

Агеев А. А. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: ageev@math.nsc.ru

Статья поступила 23 апреля 1997 г.