Please use this identifier to cite or link to this item:
https://elib.bsu.by/handle/123456789/288549| Title: | Стурктурные и алгоритмические аспекты слабых рёберных покрытий в графах |
| Other Titles: | Structural and algorithmic aspects of weak edge coverings in graphs / Y.L. Orlovich, A.D. Suraveshkin, Y.A. Kartynnik |
| Authors: | Орлович, Ю. Л. Суравежкин, А. Д. Картынник, Ю. А. |
| Keywords: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Кибернетика |
| Issue Date: | 2022 |
| Publisher: | Минск : БГУ |
| Citation: | Информационные системы и технологии = Information Systems and Technologies : материалы междунар. науч. конгресса по информатике. В 3 ч. Ч. 2, Респ. Беларусь, Минск, 27–28 окт. 2022 г. / Белорус. гос. ун-т ; редкол.: С. В. Абламейко (гл. ред.) [и др.]. – Минск : БГУ, 2022. – С. 251-258. |
| Abstract: | Подмножество рёбер графа называется слабым рёберным покрытием, если каждая вершина графа инцидентна некоторому ребру из данного подмножества или лежит в треугольнике, содержащем такое ребро. В работе предлагаются некоторые оценки для наименьшего числа рёбер в слабом рёберном покрытии графа. Доказано, что в классах расщепляемых графов и кубических графов задача нахождения слабого рёберного покрытия наименьшей мощности является NP-трудной. Рассматривается наследственный класс графов, в которых у каждого порождённого подграфа без изолированных вершин все минимальные (по включению) слабые рёберные покрытия имеют одинаковую мощность |
| Abstract (in another language): | 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 |
| Licence: | info:eu-repo/semantics/openAccess |
| Appears in Collections: | 2022. Информационные системы и технологии |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 251-258.pdf | 365,35 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.