Слабые рёберные покрытия в графах: сложность аппроксимации и наследственные свойства

Орлович, Ю. Л.; Суравежкин, А. Д.; Картынник, Ю. А.

Issue Date Author Title Subject

Please use this identifier to cite or link to this item: https://elib.bsu.by/handle/123456789/341173

Full metadata record

DC Field	Value	Language
dc.contributor.author	Орлович, Ю. Л.
dc.contributor.author	Суравежкин, А. Д.
dc.contributor.author	Картынник, Ю. А.
dc.date.accessioned	2026-02-05T11:05:05Z	-
dc.date.available	2026-02-05T11:05:05Z	-
dc.date.issued	2025
dc.identifier.citation	Информационные системы и технологии = Information Systems and Technologies : материалы XI Междунар. науч. конгр. по информатике (CSIST-2025), Респ. Беларусь, Минск, 29–31 окт. 2025 г. В 2 ч. Ч. 2 / Белорус. гос. ун-т ; редкол.: С. В. Абламейко (гл. ред.) [и др]. – Минск : БГУ, 2025. – С. 278-285.
dc.identifier.isbn	978-985-881-851-7
dc.identifier.isbn	978-985-881-853-1 (ч. 2)
dc.identifier.uri	https://elib.bsu.by/handle/123456789/341173	-
dc.description	Раздел III. Теоретическая информатика и программная инженерия
dc.description.abstract	Рассматривается задача о наименьшем слабом рёберном покрытии графа, которая представляет собой естественное обобщение классической проблемы наименьшего рёберного покрытия. В предположении P ≠ NP установлена NP-трудность задачи построения (k ln n)-приближённого решения для оптимизационной версии рассматриваемой задачи, где k > 0 – некоторая фиксированная рациональная константа и n – порядок входного графа. Получена характеризация в терминах запрещённых порождённых подграфов для наследственного класса графов, в которых у каждого порождённого подграфа без изолированных вершин все минимальные (по включению) слабые рёберные покрытия имеют одинаковую мощность
dc.language.iso	ru
dc.publisher	Минск : БГУ
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика
dc.title	Слабые рёберные покрытия в графах: сложность аппроксимации и наследственные свойства
dc.title.alternative	Weak edge covers in graphs: approximation complexity and hereditary properties / Yu. L. Orlovich, A. D. Suraveshkin, Y. A. Kartynnik
dc.type	conference paper
dc.description.alternative	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
Appears in Collections:	2025. Информационные системы и технологии

Files in This Item:

File	Description	Size	Format
278-285.pdf		556,83 kB	Adobe PDF	View/Open

Show simple item record Google Scholar