Efficient Algorithms for Reconstruction of 2D-Arrays from Extended Parikh Images

摘要

The concept of a Parikh matrix or an extended Parikh mapping of words introduced by Mateescu et al (2001) is formulated here for two-dimensional (2D) arrays. A polynomial time algorithm is proposed to reconstruct an unknown 2D-array over {0, 1} from its image under the extended Parikh mapping along a single direction. On the other hand the problem of reconstructing a 2D-array over {0,1} from its image under the extended Parikh mapping along three or more directions is shown to be NP-hard. Also a polynomial time algorithm to reconstruct a 2D-array over {0,1} with a maximum number of ones close to the main diagonal of the array is presented by reducing the problem to Min-cost Max-flow problem.