Given an undirected simple graph G with node set V and edge set E, let fv, for each node v∈ V, denote a nonnegative integer value that is lower than or equal to the degree of v in G. An f-dominating set in G is a node subset D such that for each node v∈ V D at least fv of its neighbors belong to D. In this paper, we study the polyhedral structure of the polytope defined as the convex hull of all the incidence vectors of f-dominating sets in G and give a complete description for the case of trees. We prove that the corresponding separation problem can be solved in polynomial time. In addition, we present a linear-time algorithm to solve the weighted version of the problem on trees: Given a cost cv∈ R for each node v∈ V, find an f-dominating set D in G whose cost, given by ∑ v∈Dcv, is a minimum.

On f-domination: polyhedral and algorithmic results / Dell'Amico, M.; Neto, J.. - In: MATHEMATICAL METHODS OF OPERATIONS RESEARCH. - ISSN 1432-2994. - 90:1(2019), pp. 1-22.

I documenti presenti in Iris Unimore sono rilasciati con licenza Creative Commons Attribuzione - Non commerciale - Non opere derivate 3.0 Italia, salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Powered by IRIS-about IRIS-Utilizzo dei cookie

 Copyright © 2021