2014/07/07 by Andrei Gagarin, Gagarin, Andrei, Vadim Zverovich +1
Computer Science · Mathematics · #05C69 #05C70 #05C85 #68R10 #68W20 #90B10 #90B15 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:05C69 #msc:05C70 #msc:05C85 #msc:68R10 #msc:68W20 #msc:90B10 #msc:90B15
paper · pdf · doi:10.48550/arxiv.1407.1637
extended abstract, 4 pages, Proc. 9th International Colloquium on Graph Theory and Combinatorics, ICGT 2014, Grenoble, France, June 30-July 4, 2014, paper no.27
arxiv created 2014/07/07 · arxiv updated 2014/07/08
We consider (closed neighbourhood) packings and their generalization in graphs called limited packings. A vertex set X in a graph G is a k-limited packing if for any vertex v∈ V(G), |N[v] ∩ X| ≤ k, where N[v] is the closed neighbourhood of v. The k-limited packing number Lk(G) is the largest size of a k-limited packing in G. Limited packing problems can be considered as secure facility location problems in networks. We develop probabilistic and greedy approaches to limited packings in graphs, providing lower bounds for the k-limited packing number, and randomized and greedy algorithms to find k-limited packings satisfying the bounds. Some upper bounds for Lk(G) are given as well. The problem of finding a maximum size k-limited packing is known to be NP-complete even in split or bipartite graphs.