Please use this identifier to cite or link to this item:
https://elib.bsu.by/handle/123456789/341173| Title: | Слабые рёберные покрытия в графах: сложность аппроксимации и наследственные свойства |
| Other Titles: | Weak edge covers in graphs: approximation complexity and hereditary properties / Yu. L. Orlovich, A. D. Suraveshkin, Y. A. Kartynnik |
| Authors: | Орлович, Ю. Л. Суравежкин, А. Д. Картынник, Ю. А. |
| Keywords: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика |
| Issue Date: | 2025 |
| Publisher: | Минск : БГУ |
| Citation: | Информационные системы и технологии = Information Systems and Technologies : материалы XI Междунар. науч. конгр. по информатике (CSIST-2025), Респ. Беларусь, Минск, 29–31 окт. 2025 г. В 2 ч. Ч. 2 / Белорус. гос. ун-т ; редкол.: С. В. Абламейко (гл. ред.) [и др]. – Минск : БГУ, 2025. – С. 278-285. |
| Abstract: | Рассматривается задача о наименьшем слабом рёберном покрытии графа, которая представляет собой естественное обобщение классической проблемы наименьшего рёберного покрытия. В предположении P ≠ NP установлена NP-трудность задачи построения (k ln n)-приближённого решения для оптимизационной версии рассматриваемой задачи, где k > 0 – некоторая фиксированная рациональная константа и n – порядок входного графа. Получена характеризация в терминах запрещённых порождённых подграфов для наследственного класса графов, в которых у каждого порождённого подграфа без изолированных вершин все минимальные (по включению) слабые рёберные покрытия имеют одинаковую мощность |
| Abstract (in another language): | The minimum weak edge cover problem, which is a natural generalization of the classical minimum edge cover problem, is considered. The NP-hardness of the problem of constructing (k ln n)-approximate solution for the optimization version of the problem under consideration is established, where k > 0 is a fixed rational constant and n is the order of the input graph. A characterization in terms of forbidden induced subgraphs is obtained for the hereditary class of graphs in which for every induced subgraph without isolated vertices all minimal (by inclusion) weak edge covers have the same cardinality |
| Description: | Раздел III. Теоретическая информатика и программная инженерия |
| URI: | https://elib.bsu.by/handle/123456789/341173 |
| ISBN: | 978-985-881-851-7 978-985-881-853-1 (ч. 2) |
| Licence: | info:eu-repo/semantics/openAccess |
| Appears in Collections: | 2025. Информационные системы и технологии |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 278-285.pdf | 556,83 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.