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 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

[thumbnail of GZ_DAM_2014_revised_v5a.pdf]
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: 08 Nov 2023 03: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 Edit Item

Downloads

Downloads per month over past year

View more statistics