Фрагментарные модели для некоторых экстремальных задач на графах

• Veröffentlicht in: Математичні машини і системи
• Datum: 2014
• Hauptverfasser: Козин, И.В., Полюга, С.И.
• Format: Artikel
• Sprache: Russisch
• Veröffentlicht: Інститут проблем математичних машин і систем НАН України 2014
• Schlagworte: Моделювання і управління
• Online Zugang: https://nasplib.isofts.kiev.ua/handle/123456789/84341
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Zitieren: Фрагментарные модели для некоторых экстремальных задач на графах / И.В. Козин, С.И. Полюга // Математичні машини і системи. — 2014. — № 1. — С. 143-150. — Бібліогр.: 7 назв. — рос.

В статье предложены фрагментарные модели для трех классических экстремальных задач на графах: о вершинном покрытии, доминирующем множестве и о клике. Показана достижимость оптимальных решений этих задач в рамках фрагментарной модели. Предложены приближенные алгоритмы поиска решений этих задач на основе фрагментарной структуры. У статті запропоновані фрагментарні моделі для трьох класичних екстремальних задач на графах: про вершинне покриття, домінуючу множину і про кліку. Показано досяжність оптимальних рішень цих задач у рамках фрагментарної моделі. Запропоновано наближені алгоритми пошуку рішень цих задач на основі фрагментарної структури. 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.