Bounds and algorithms for limited packings in graphs

arXiv1407.1637MaRDI QIDQ6252924FDOQ6252924

Vadim Zverovich, Andrei Gagarin

Publication date: 7 July 2014

Abstract: 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 $vinV(G)$, $left|N[v]capXight|lek$, where $N[v]$ is the closed neighbourhood of $v$. The k-limited packing number $L_k(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 $L_k(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.

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Deterministic network models in operations research (90B10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Stochastic network models in operations research (90B15)

This page was built for publication: Bounds and algorithms for limited packings in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6252924)