Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/288549Полная запись метаданных
| Поле DC | Значение | Язык |
|---|---|---|
| dc.contributor.author | Орлович, Ю. Л. | - |
| dc.contributor.author | Суравежкин, А. Д. | - |
| dc.contributor.author | Картынник, Ю. А. | - |
| dc.date.accessioned | 2022-11-09T09:27:14Z | - |
| dc.date.available | 2022-11-09T09:27:14Z | - |
| dc.date.issued | 2022 | - |
| dc.identifier.citation | Информационные системы и технологии = Information Systems and Technologies : материалы междунар. науч. конгресса по информатике. В 3 ч. Ч. 2, Респ. Беларусь, Минск, 27–28 окт. 2022 г. / Белорус. гос. ун-т ; редкол.: С. В. Абламейко (гл. ред.) [и др.]. – Минск : БГУ, 2022. – С. 251-258. | - |
| dc.identifier.isbn | 978-985-881-425-0 (ч. 2); ISBN 978-985-881-427-4 | - |
| dc.identifier.uri | https://elib.bsu.by/handle/123456789/288549 | - |
| dc.description.abstract | Подмножество рёбер графа называется слабым рёберным покрытием, если каждая вершина графа инцидентна некоторому ребру из данного подмножества или лежит в треугольнике, содержащем такое ребро. В работе предлагаются некоторые оценки для наименьшего числа рёбер в слабом рёберном покрытии графа. Доказано, что в классах расщепляемых графов и кубических графов задача нахождения слабого рёберного покрытия наименьшей мощности является NP-трудной. Рассматривается наследственный класс графов, в которых у каждого порождённого подграфа без изолированных вершин все минимальные (по включению) слабые рёберные покрытия имеют одинаковую мощность | - |
| dc.language.iso | ru | - |
| dc.publisher | Минск : БГУ | - |
| dc.rights | info:eu-repo/semantics/openAccess | - |
| dc.subject | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Кибернетика | - |
| dc.title | Стурктурные и алгоритмические аспекты слабых рёберных покрытий в графах | - |
| dc.title.alternative | Structural and algorithmic aspects of weak edge coverings in graphs / Y.L. Orlovich, A.D. Suraveshkin, Y.A. Kartynnik | - |
| dc.type | conference paper | - |
| dc.description.alternative | 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 | - |
| Располагается в коллекциях: | 2022. Информационные системы и технологии | |
Полный текст документа:
| Файл | Описание | Размер | Формат | |
|---|---|---|---|---|
| 251-258.pdf | 365,35 kB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.