Свойства бесперспективных максимальных замкнутых множеств
Рассмотрена классическая труднорешаемая задача комбинаторной оптимизации «Максимальное независимое множество». Данная задача имеет обширную область применения в различных теоретических и практических приложениях. Ранее автором были определены новые свойства оптимального решения з...
Gespeichert in:
| Datum: | 2003 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут проблем математичних машин і систем НАН України
2003
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/733 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Свойства бесперспективных максимальных замкнутых множеств / Аксенова Л.А. // Математические машины и системы. – 2003. – № 3, 4. – С. 43 – 50. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862728566607708160 |
|---|---|
| author | Аксенова, Л.А. |
| author_facet | Аксенова, Л.А. |
| citation_txt | Свойства бесперспективных максимальных замкнутых множеств / Аксенова Л.А. // Математические машины и системы. – 2003. – № 3, 4. – С. 43 – 50. |
| collection | DSpace DC |
| description | Рассмотрена классическая труднорешаемая задача комбинаторной оптимизации «Максимальное независимое множество». Данная задача имеет обширную область применения в различных теоретических и практических приложениях. Ранее автором были определены новые свойства оптимального решения задачи, введено понятие покрытия вершины и рассмотрен точный алгоритм его определения посредством анализа максимальных замкнутых множеств. В данной статье выведены новые свойства бесперспективных максимальных замкнутых множеств и предложены новые правила отсечения избыточных ветвей алгоритма. Данные правила позволяют уменьшить дерево вариантов и сократить объем необходимых вычислений. Ил.: 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.
|
| first_indexed | 2025-12-07T19:09:19Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-733 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Russian |
| last_indexed | 2025-12-07T19:09:19Z |
| publishDate | 2003 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Аксенова, Л.А. 2008-06-24T13:33:44Z 2008-06-24T13:33:44Z 2003 Свойства бесперспективных максимальных замкнутых множеств / Аксенова Л.А. // Математические машины и системы. – 2003. – № 3, 4. – С. 43 – 50. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/733 681.513 Рассмотрена классическая труднорешаемая задача комбинаторной оптимизации «Максимальное независимое множество». Данная задача имеет обширную область применения в различных теоретических и практических приложениях. Ранее автором были определены новые свойства оптимального решения задачи, введено понятие покрытия вершины и рассмотрен точный алгоритм его определения посредством анализа максимальных замкнутых множеств. В данной статье выведены новые свойства бесперспективных максимальных замкнутых множеств и предложены новые правила отсечения избыточных ветвей алгоритма. Данные правила позволяют уменьшить дерево вариантов и сократить объем необходимых вычислений. Ил.: 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. ru Інститут проблем математичних машин і систем НАН України Обчислювальні системи Свойства бесперспективных максимальных замкнутых множеств Властивості бесперспективних максимальних замкнених множин The properties of non-perspective maximal closed sets Article published earlier |
| spellingShingle | Свойства бесперспективных максимальных замкнутых множеств Аксенова, Л.А. Обчислювальні системи |
| title | Свойства бесперспективных максимальных замкнутых множеств |
| title_alt | Властивості бесперспективних максимальних замкнених множин The properties of non-perspective maximal closed sets |
| title_full | Свойства бесперспективных максимальных замкнутых множеств |
| title_fullStr | Свойства бесперспективных максимальных замкнутых множеств |
| title_full_unstemmed | Свойства бесперспективных максимальных замкнутых множеств |
| title_short | Свойства бесперспективных максимальных замкнутых множеств |
| title_sort | свойства бесперспективных максимальных замкнутых множеств |
| topic | Обчислювальні системи |
| topic_facet | Обчислювальні системи |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/733 |
| work_keys_str_mv | AT aksenovala svoistvabesperspektivnyhmaksimalʹnyhzamknutyhmnožestv AT aksenovala vlastivostíbesperspektivnihmaksimalʹnihzamknenihmnožin AT aksenovala thepropertiesofnonperspectivemaximalclosedsets |