ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Публикационная активность

(сведения по итогам 2017 г.)
2-летний импакт-фактор РИНЦ: 0,500
2-летний импакт-фактор РИНЦ без самоцитирования: 0,405
Двухлетний импакт-фактор РИНЦ с учетом цитирования из всех
источников: 0,817
5-летний импакт-фактор РИНЦ: 0,319
5-летний импакт-фактор РИНЦ без самоцитирования: 0,264
Суммарное число цитирований журнала в РИНЦ: 6012
Пятилетний индекс Херфиндаля по цитирующим журналам: 404
Индекс Херфиндаля по организациям авторов: 338
Десятилетний индекс Хирша: 17
Место в общем рейтинге SCIENCE INDEX за 2017 год: 527
Место в рейтинге SCIENCE INDEX за 2017 год по тематике "Автоматика. Вычислительная техника": 16

Больше данных по публикационной активности нашего журнале за 2008-2017 гг. на сайте РИНЦ

Добавить в закладки

Следующий номер на сайте

2
Ожидается:
16 Июня 2019

В институте математики Сибирского федерального университета предложен новый полиномиальный по времени эвристический алгоритм, основанный на пополнении гиперграфа до ациклического

18.05.2011

Структура многих NP-трудных задач комбинаторной оптимизации может быть описана гиперграфом. Такие задачи возникают в системах принятия решений, БД, при анализе информационных и коммуникационных сетей, конструкторском проектировании радиоэлектронной и вычислительной аппаратуры, лингвистической трансляции, при формировании трафика компьютерных сетей и т.д. Дерево декомпозиции гиперграфа дает возможность организовать процесс поиска оптимального решения по принципу «разделяй и властвуй». Если древовидная ширина гиперграфа ограничена сверху некоторой константой, то многие NP-трудные задачи комбинаторной оптимизации могут быть решены за полиномиальное время. Древовидная ширина – это числовая характеристика гиперграфа, определяемая через оптимальное дерево декомпозиции. К сожалению, сама задача нахождения оптимального дерева декомпозиции также NP-трудная, поэтому в алгоритмической практике востребованы эвристики, позволяющие получать хорошие деревья декомпозиции за разумное время. 

Предлагается эвристический алгоритм CTDA (Computing Tree Decomposition by Acyclicity), основанный на пополнении гиперграфа до М-ациклического. Свойство М-ацикличности (называемое также a-ацикличностью) широко эксплуатируется в различных приложениях теории гиперграфов, так как обеспечивает полиномиальную вычислимость ряда важных характеристик и графических конструкций, связанных с гиперграфами. Употребление данного свойства в алгоритме CTDA дает возможность создавать за полиномиальное время дерево декомпозиции гиперграфа с разной степенью приближения к оптимальному дереву декомпозиции. 

Подробное описание дается в статье «Алгоритм построения дерева декомпозиции гиперграфа на основе ацикличности», автор Быкова В.В. (Институт математики Сибирского федерального университета, г. Красноярск).