2018/03/08 by Jozef Kratica, Kratica, Jozef J., Aleksandar Lj. Savić +3
Computer Science · Engineering · #05C12 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Packing Problems #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.1803.03147
openalex publication_date 2018/03/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The recently introduced \k\-packing function problem is considered in this paper. Special relation between a case when k=1, k≥ 2 and linear programming relaxation is introduced with sufficient conditions for optimality. For arbitrary simple connected graph G there is construction procedure for finding values of k for which L_\k\(G) can be determined in the polynomial time. Additionally, relationship between \1\-packing function and independent set number is established. Optimal values for some special classes of graphs and general upper and lower bounds are introduced.