Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/288549| Заглавие документа: | Стурктурные и алгоритмические аспекты слабых рёберных покрытий в графах |
| Другое заглавие: | Structural and algorithmic aspects of weak edge coverings in graphs / Y.L. Orlovich, A.D. Suraveshkin, Y.A. Kartynnik |
| Авторы: | Орлович, Ю. Л. Суравежкин, А. Д. Картынник, Ю. А. |
| Тема: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Кибернетика |
| Дата публикации: | 2022 |
| Издатель: | Минск : БГУ |
| Библиографическое описание источника: | Информационные системы и технологии = Information Systems and Technologies : материалы междунар. науч. конгресса по информатике. В 3 ч. Ч. 2, Респ. Беларусь, Минск, 27–28 окт. 2022 г. / Белорус. гос. ун-т ; редкол.: С. В. Абламейко (гл. ред.) [и др.]. – Минск : БГУ, 2022. – С. 251-258. |
| Аннотация: | Подмножество рёбер графа называется слабым рёберным покрытием, если каждая вершина графа инцидентна некоторому ребру из данного подмножества или лежит в треугольнике, содержащем такое ребро. В работе предлагаются некоторые оценки для наименьшего числа рёбер в слабом рёберном покрытии графа. Доказано, что в классах расщепляемых графов и кубических графов задача нахождения слабого рёберного покрытия наименьшей мощности является NP-трудной. Рассматривается наследственный класс графов, в которых у каждого порождённого подграфа без изолированных вершин все минимальные (по включению) слабые рёберные покрытия имеют одинаковую мощность |
| Аннотация (на другом языке): | A subset of edges of a graph is called weak edge cover if each vertex of the graph is incident to an edge of this subset or is lying in a triangle containing such an edge. Estimates for the minimum number of edges in a weak edge cover of a graph are proposed. It is proved that for the classes of split graphs and cubic graphs the problem of finding a weak edge cover of minimum cardinality is NP-hard. The hereditary class of graphs in which for every isolate-free induced subgraph all its minimal (by inclusion) weak edge covers have the same cardinality is considered |
| URI документа: | https://elib.bsu.by/handle/123456789/288549 |
| ISBN: | 978-985-881-425-0 (ч. 2); ISBN 978-985-881-427-4 |
| Лицензия: | info:eu-repo/semantics/openAccess |
| Располагается в коллекциях: | 2022. Информационные системы и технологии |
Полный текст документа:
| Файл | Описание | Размер | Формат | |
|---|---|---|---|---|
| 251-258.pdf | 365,35 kB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.