Свойства бесперспективных максимальных замкнутых множеств

Рассмотрена классическая труднорешаемая задача комбинаторной оптимизации «Максимальное независимое множество». Данная задача имеет обширную область применения в различных теоретических и практических приложениях. Ранее автором были определены новые свойства оптимального решения з...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2003
Автор:	Аксенова, Л.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут проблем математичних машин і систем НАН України 2003
Теми:	Обчислювальні системи
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/733
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Свойства бесперспективных максимальных замкнутых множеств / Аксенова Л.А. // Математические машины и системы. – 2003. – № 3, 4. – С. 43 – 50.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-733
record_format	dspace
spelling	irk-123456789-7332008-06-25T12:00:21Z Свойства бесперспективных максимальных замкнутых множеств Аксенова, Л.А. Обчислювальні системи Рассмотрена классическая труднорешаемая задача комбинаторной оптимизации «Максимальное независимое множество». Данная задача имеет обширную область применения в различных теоретических и практических приложениях. Ранее автором были определены новые свойства оптимального решения задачи, введено понятие покрытия вершины и рассмотрен точный алгоритм его определения посредством анализа максимальных замкнутых множеств. В данной статье выведены новые свойства бесперспективных максимальных замкнутых множеств и предложены новые правила отсечения избыточных ветвей алгоритма. Данные правила позволяют уменьшить дерево вариантов и сократить объем необходимых вычислений. Ил.: 2. Библиогр.: 7 назв. Розглянута класична важковирішувана задача комбінаторної оптимізації “Максимальна незалежна множина”. Ця задача має обширну галузь застосування у різноманітних теоретичних та практичних додатках. Раніше автором були визначені нові властивості оптимального рішення задачі, введено поняття покриття вершини та розглянуто точний алгоритм його визначення за допомогою аналізу максимальних замкнених множин. У поданій статті визначені нові властивості бесперспективних максимальних замкнених множин та запропановано нові правила відсікань збиткових гілок алгоритму. Ці правила дозволять зменшити дерево варіантів та скоротити об’єм необхідних обчислень. Іл.: 2. Бібліогр.: 7 назв. The classical intractable problem of combinatorial optimisation “Maximum independent set” is considered. The problem has many possibilities of use in different theoretical and practical applications. In the previous works the author has defined the new properties of optimal problem solution, introduced the term of the node cover and considered the exact algorithm for its determination analysing maximal closed sets. There were derived the new properties for non-perspective maximal closed sets and the new cutting rules for redundant algorithm’s branches were proposed. The given rules allow to decrease the variant tree and amount of necessary calculation. Figs.: 2. Refs.: 7 titles. 2003 Article Свойства бесперспективных максимальных замкнутых множеств / Аксенова Л.А. // Математические машины и системы. – 2003. – № 3, 4. – С. 43 – 50. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/733 681.513 ru Інститут проблем математичних машин і систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Обчислювальні системи Обчислювальні системи
spellingShingle	Обчислювальні системи Обчислювальні системи Аксенова, Л.А. Свойства бесперспективных максимальных замкнутых множеств
description	Рассмотрена классическая труднорешаемая задача комбинаторной оптимизации «Максимальное независимое множество». Данная задача имеет обширную область применения в различных теоретических и практических приложениях. Ранее автором были определены новые свойства оптимального решения задачи, введено понятие покрытия вершины и рассмотрен точный алгоритм его определения посредством анализа максимальных замкнутых множеств. В данной статье выведены новые свойства бесперспективных максимальных замкнутых множеств и предложены новые правила отсечения избыточных ветвей алгоритма. Данные правила позволяют уменьшить дерево вариантов и сократить объем необходимых вычислений. Ил.: 2. Библиогр.: 7 назв.
format	Article
author	Аксенова, Л.А.
author_facet	Аксенова, Л.А.
author_sort	Аксенова, Л.А.
title	Свойства бесперспективных максимальных замкнутых множеств
title_short	Свойства бесперспективных максимальных замкнутых множеств
title_full	Свойства бесперспективных максимальных замкнутых множеств
title_fullStr	Свойства бесперспективных максимальных замкнутых множеств
title_full_unstemmed	Свойства бесперспективных максимальных замкнутых множеств
title_sort	свойства бесперспективных максимальных замкнутых множеств
publisher	Інститут проблем математичних машин і систем НАН України
publishDate	2003
topic_facet	Обчислювальні системи
url	http://dspace.nbuv.gov.ua/handle/123456789/733
citation_txt	Свойства бесперспективных максимальных замкнутых множеств / Аксенова Л.А. // Математические машины и системы. – 2003. – № 3, 4. – С. 43 – 50.
work_keys_str_mv	AT aksenovala svojstvabesperspektivnyhmaksimalʹnyhzamknutyhmnožestv
first_indexed	2023-03-24T08:19:35Z
last_indexed	2023-03-24T08:19:35Z
_version_	1796138821896634368

Свойства бесперспективных максимальных замкнутых множеств

Репозитарії

Схожі ресурси