Maximally recoverable codes: Connections to generic network coding and maximal matching
Chi Wan Sung, Kenneth W. Shum, Quan Gang Yu, Guangping Xu · 2017
The instantiation of a maximally recoverable (MR) code is shown to be a special case of generic network coding. The defining condition of MR codes, called potential independence, is shown to be equivalent to maximal matching in bipartite graphs. Algorithms for MR instantiation are proposed and upper bounds on the required field size are derived.