engleski

Block allocation of a sequential resource

An $H$-packing of $G$ is a collection of vertex-disjoint subgraphs of $G$ such that each component is isomorphic to $H$. An $H$-packing of $G$ is maximal if it cannot be extended to a larger $H$-packing of $G$. In this paper we consider problem of random allocation of a sequential resource into blocks of $m$ consecutive units and show how it can be successfully modeled in terms of maximal $P_m$-packings. We enumerate maximal $P_m$-packings of $P_n$ of a given cardinality and determine the asymptotic behavior of the enumerating sequences. We also compute the expected size of $m$-packings and provide a lower bound on the efficiency of block-allocation.

maximal matching ; maximal packing

nije evidentirano