Given a positive integer k and a graph G, a k-limited packing in G (2010) is a subset B of its vertex set such that each closed neighborhood has at most k vertices of B. As a variation, we introduce the notion of a {k}-packing function f of G which assigns a non-negative integer to the vertices of G in such a way that the sum of f(v) over each closed neighborhood is at most k. For fixed k, we prove that the problem of finding a {k}-packing function of maximum weight ({k}PF) can be reduced linearly to the problem of finding a k-limited packing of maximum cardinality (kLP). We present an O(|V(G)| + |E(G)|) time algorithm to solve {k}PF on strongly chordal graphs. We also use monadic second-order logic to prove that both problems are linear time solvable for graphs with clique-width bounded by a constant.
展开▼
