М-АЦИКЛИЧЕСКИЕ И ДРЕВОВИДНЫЕ ГИПЕРГРАФЫ : научное издание

Описание

Тип публикации: статья из журнала

Год издания: 2010

Ключевые слова: реализация гиперграфа деревом, дерево соединений гиперграфа, древовидная декомпозиция задач дискретной оптимизации, полиномиальные вычисления, tree realization hypergraph, tree compounds hypergraph, tree decomposition of problem discrete optimization, Polynomial computations

Аннотация: Приводится характеризация двух классов гиперграфов: М-ациклических и древовидных. Установлена связь между этими классами: гиперграф М-ацикличен тогда и только тогда, когда двойственный к нему гиперграф является древовидным. Эта связь дает возможность объединить арсенал известных полиномиальных алгоритмов, позволяющих распознавать пПоказать полностьюринадлежность гиперграфа к указанным классам и строить деревья соединений, деревья декомпозиций и деревья реализаций гиперграфа. The characterization of two classes of hypergraphs: M-acyclic and tree has been given. The link between these two classes: a hypergraph is M-acyclic if and only if the hypergraph dual to it is a tree was established. This relationship provides an opportunity to join the arsenal of known polynomial algorithms allowing detecting hypergraph belonging to these classes and building the trees of compounds, decompositions and trees of hypergraph realization.

Ссылки на полный текст

Издание

Журнал: Известия Томского политехнического университета. Инжиниринг георесурсов

Выпуск журнала: Т. 317, 2

Номера страниц: 25-30

ISSN журнала: 25001019

Место издания: Томск

Издатель: Федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский Томский политехнический университет"

Авторы

Вхождение в базы данных