The probabilistic approach to limited packings in graphs

Gagarin, Andrei ORCID: https://orcid.org/0000-0001-9749-9706 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

Preview

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

Abstract

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:	22 Nov 2024 10:15
URI:	https://orca.cardiff.ac.uk/id/eprint/91296

Citation Data

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

Actions (repository staff only)

Edit Item