Abstract:
We study the multidimensional constrained systems of Zd-permutations with restricted movement. We show a correspondence between these restricted permutations and perfect ...Show MoreMetadata
Abstract:
We study the multidimensional constrained systems of Zd-permutations with restricted movement. We show a correspondence between these restricted permutations and perfect matchings. We use the theory of perfect matchings to investigate several two-dimensional cases, for which we compute the exact capacity of the constrained system, and prove the existence of a polynomial-time algorithm for counting admissible patterns. We prove that the capacity of Zd-permutations restricted by a set with full affine dimension depends only on the size of the set. We use this result in order to compute the exact capacity for a class of two-dimensional constrained systems.
Date of Conference: 21-26 June 2020
Date Added to IEEE Xplore: 24 August 2020
ISBN Information: