On total f-domination: Polyhedral and algorithmic results

作     者：Dell'Amico, Mauro Neto, Jose 

作者机构：Univ Modena & Reggio Emilia Dept Sci & Methods Engn Via Amendola 2 I-42122 Reggio Emilia Italy Univ Paris Saclay CNRS Telecom SudParis Samovar 9 Rue Charles Fourier F-91011 Evry France 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2019年第258卷

页      面：97-104页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：EC-FP7 COST Action [TD1207] 

主　　题：Total domination Polytope Tree Linear-time algorithm 

摘      要：Given a graph G = (V, E) and integer values f(v), v is an element of V, a node subset D subset of V is a total f -dominating set if every node v is an element of V is adjacent to at least f(v) nodes of D. Given a weight system c(v), v is an element of V, the minimum weight total f-dominating set problem is to find a total f-dominating set of minimum total weight. In this article, we propose a polyhedral study of the associated polytope together with a complete and compact description of the polytope for totally unimodular graphs and cycles. We also propose a linear time dynamic programming algorithm for the case of trees. (C) 2018 Elsevier B.V. All rights reserved.