Фрагментарные модели для некоторых экстремальных задач на графах
В статье предложены фрагментарные модели для трех классических экстремальных задач на графах: о вершинном покрытии, доминирующем множестве и о клике. Показана достижимость оптимальных решений этих задач в рамках фрагментарной модели. Предложены приближенные алгоритмы поиска решений этих задач на осн...
Saved in:
| Published in: | Математичні машини і системи |
|---|---|
| Date: | 2014 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем математичних машин і систем НАН України
2014
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84341 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Фрагментарные модели для некоторых экстремальных задач на графах / И.В. Козин, С.И. Полюга // Математичні машини і системи. — 2014. — № 1. — С. 143-150. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862710315459805184 |
|---|---|
| author | Козин, И.В. Полюга, С.И. |
| author_facet | Козин, И.В. Полюга, С.И. |
| citation_txt | Фрагментарные модели для некоторых экстремальных задач на графах / И.В. Козин, С.И. Полюга // Математичні машини і системи. — 2014. — № 1. — С. 143-150. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| description | В статье предложены фрагментарные модели для трех классических экстремальных задач на графах: о вершинном покрытии, доминирующем множестве и о клике. Показана достижимость оптимальных решений этих задач в рамках фрагментарной модели. Предложены приближенные алгоритмы поиска решений этих задач на основе фрагментарной структуры.
У статті запропоновані фрагментарні моделі для трьох класичних екстремальних задач на графах: про вершинне покриття, домінуючу множину і про кліку. Показано досяжність оптимальних рішень цих задач у рамках фрагментарної моделі. Запропоновано наближені алгоритми пошуку рішень цих задач на основі фрагментарної структури.
The article suggests fragmentary models for three classical extremal problems on graphs: the vertex cover, dominating set and the clique. The achievability of optimal solutions of these problems in the fragmentary model is shown. Approximate algorithms of finding solutions of these problems on the basis of fragmentary structure are suggested.
|
| first_indexed | 2025-12-07T17:23:08Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-84341 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Russian |
| last_indexed | 2025-12-07T17:23:08Z |
| publishDate | 2014 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Козин, И.В. Полюга, С.И. 2015-07-06T16:21:11Z 2015-07-06T16:21:11Z 2014 Фрагментарные модели для некоторых экстремальных задач на графах / И.В. Козин, С.И. Полюга // Математичні машини і системи. — 2014. — № 1. — С. 143-150. — Бібліогр.: 7 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/84341 519.8 В статье предложены фрагментарные модели для трех классических экстремальных задач на графах: о вершинном покрытии, доминирующем множестве и о клике. Показана достижимость оптимальных решений этих задач в рамках фрагментарной модели. Предложены приближенные алгоритмы поиска решений этих задач на основе фрагментарной структуры. У статті запропоновані фрагментарні моделі для трьох класичних екстремальних задач на графах: про вершинне покриття, домінуючу множину і про кліку. Показано досяжність оптимальних рішень цих задач у рамках фрагментарної моделі. Запропоновано наближені алгоритми пошуку рішень цих задач на основі фрагментарної структури. The article suggests fragmentary models for three classical extremal problems on graphs: the vertex cover, dominating set and the clique. The achievability of optimal solutions of these problems in the fragmentary model is shown. Approximate algorithms of finding solutions of these problems on the basis of fragmentary structure are suggested. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Моделювання і управління Фрагментарные модели для некоторых экстремальных задач на графах Фрагментарні моделі для деяких екстремальних задач на графах Fragmentary models for some extremal problems on graphs Article published earlier |
| spellingShingle | Фрагментарные модели для некоторых экстремальных задач на графах Козин, И.В. Полюга, С.И. Моделювання і управління |
| title | Фрагментарные модели для некоторых экстремальных задач на графах |
| title_alt | Фрагментарні моделі для деяких екстремальних задач на графах Fragmentary models for some extremal problems on graphs |
| title_full | Фрагментарные модели для некоторых экстремальных задач на графах |
| title_fullStr | Фрагментарные модели для некоторых экстремальных задач на графах |
| title_full_unstemmed | Фрагментарные модели для некоторых экстремальных задач на графах |
| title_short | Фрагментарные модели для некоторых экстремальных задач на графах |
| title_sort | фрагментарные модели для некоторых экстремальных задач на графах |
| topic | Моделювання і управління |
| topic_facet | Моделювання і управління |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84341 |
| work_keys_str_mv | AT koziniv fragmentarnyemodelidlânekotoryhékstremalʹnyhzadačnagrafah AT polûgasi fragmentarnyemodelidlânekotoryhékstremalʹnyhzadačnagrafah AT koziniv fragmentarnímodelídlâdeâkihekstremalʹnihzadačnagrafah AT polûgasi fragmentarnímodelídlâdeâkihekstremalʹnihzadačnagrafah AT koziniv fragmentarymodelsforsomeextremalproblemsongraphs AT polûgasi fragmentarymodelsforsomeextremalproblemsongraphs |