文章基本信息

标题：Reducing the Domination Number of Graphs via Edge Contractions
本地全文：下载
作者：Esther Galby ; Paloma T. Lima ; Bernard Ries 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：138
页码：1-13
DOI：10.4230/LIPIcs.MFCS.2019.41
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In this paper, we study the following problem: given a connected graph G, can we reduce the domination number of G by at least one using k edge contractions, for some fixed integer k >= 0? We show that for k = 1, the problem is polynomial-time solvable for P_5-free graphs and that it can be solved in FPT-time and XP-time when parameterized by tree-width and mim-width, respectively.
关键词：domination number; blocker problem; graph classes