Labelled packing functions in graphs

作     者：Hinrichsen, Erica G. Leoni, Valeria A. Safe, Martin D. 

作者机构：Univ Nacl Rosario Dept Matemat Rosario Santa Fe Argentina Consejo Nacl Invest Cient & Tecn Buenos Aires DF Argentina Univ Nacl Sur Dept Matemat Bahia Blanca Buenos Aires Argentina Univ Nacl Sur CONICET INMABB Bahia Blanca Buenos Aires Argentina 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2020年第154卷

页      面：105863-000页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：PICT ANPCyT [2016-0410] ANPCyT [PICT-2017-1315] Universidad Nacional del Sur [PGI 24/L103, 24/L115] 1ING504 

主　　题：Computational complexity Labelled packing problem Strongly chordal graph Linear time algorithm Clique-independence 

摘      要：Given a positive integer k and a graph G, a k-limited packing in G is a subset B of its vertex set such that each closed vertex neighborhood of G has at most k vertices of B (Gallant et al., 2010). A first generalization of this concept deals with a subset of vertices that cannot be in the set B and also, the number k is not a constant but it depends on the vertex neighborhood (Dobson et al., 2010). As another variation, a (k}-packing function f of G assigns a non-negative integer to the vertices of G in such a way that the sum of the values of f over each closed vertex neighborhood is at most k (Hinrichsen et al., 2014). The three associated decision problems are NP-complete in the general case. We introduce L-packing functions as a unified notion that generalizes all limited packing concepts introduced up to now. We present a linear time algorithm that solves the problem of finding the maximum weight of an L-packing function in strongly chordal graphs when a strong elimination ordering is given that includes the linear algorithm for {k}-packing functions in strongly chordal graphs (2014). Besides, we show how the algorithm can be used to solve the known clique-independence problem on strongly chordal graphs in linear time (G. Chang et al., 1993). (C) 2019 Published by Elsevier B.V.