%0 Journal Article
%T New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling
%J Algorithms | An Open Access Journal from MDPI
%D 2019
%R https://doi.org/10.3390/a12070142
%X For many parallel and distributed systems, automatic data redistribution improves its locality and increases system performance for various computer problems and applications. In general, an array can be distributed to multiple processing systems by using regular or irregular distributions. Some data distribution adopts BLOCK, CYCLIC, or BLOCK-CYCLIC to specify data array decomposition and distribution. On the other hand, irregular distributions specify a different-size data array distribution according to user-defined commands or procedures. In this work, we propose three bipartite graph problems, including the ˇ°maximum edge coloring problemˇ±, the ˇ°maximum degree edge coloring problemˇ±, and the ˇ°cost-sharing maximum edge coloring problemˇ± to formulate these kinds of distribution problems. Next, we propose an approximation algorithm with a ratio bound of two for the maximum edge coloring problem when the input graph is biplanar. Moreover, we also prove that the ˇ°cost-sharing maximum edge coloring problemˇ± is an NP-complete problem even when the input graph is biplanar. View Full-Tex
%U https://www.mdpi.com/1999-4893/12/7/142