Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
13430722 | Discrete Applied Mathematics | 2019 | 8 Pages |
Abstract
Given a graph G=(V,E)
and integer values fv, vâV, a node subset DâV is a total f-dominating set if every node vâV is adjacent to at least fv nodes of D. Given a weight system c(v), vâ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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mauro Dell'Amico, José Neto,