Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

The probabilistic approach to limited packings in graphs

Gagarin, Andrei and Zverovich, Vadim 2015. The probabilistic approach to limited packings in graphs. Discrete Applied Mathematics 184 , pp. 146-153. 10.1016/j.dam.2014.11.017

PDF - Accepted Post-Print Version
Download (271kB) | Preview


We consider (closed neighbourhood) packings and their generalization in graphs. The $k$-limited packing number L_k(G) of a graph 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. In this paper, we develop a new application of the probabilistic method to limited packings in graphs, resulting in lower bounds for the k-limited packing number and a randomized algorithm to find k-limited packings satisfying the bounds. Also, some other upper and lower bounds for L_k(G) are given.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Mathematics
Subjects: Q Science > QA Mathematics
Publisher: Elsevier
Date of First Compliant Deposit: 1 June 2016
Date of Acceptance: 17 November 2014
Last Modified: 04 Jun 2017 11:52

Citation Data

Cited 3 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics