# New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling
## 1 Introduction
As a result, there is an edge with a weight 15 and another edge with a weight 9 in the distribution graph to indicate these two communications in Figure 4.  
Figure 1: An example for \(BC(1,4,4)\). Most parallel computer programming languages supply run-time primitives or instructions to reallocate the array distribution of a program. Consequently, designing effective algorithms to do array redistribution is crucial for implementing distributed memory system software for these programming languages. In addition to array redistribution in parallel systems, in recent years, different data redistribution issues also received a lot of attention, including data redistribution in wireless sensor networks to minimize power consumption [5], data redistribution and retrieval in wireless sensor networks to preserve data [6], data redistribution in parallel join operations in distributed system [7], data distribution without breaking its semantics [8], data redistribution of data between processes [9], co-optimized application-level data movement and network-level data communications for distributed operators [10]. In this work, a bipartite graph is used to model data redistributions. Notice that a data redistribution is modeled by a bipartite graph \(G=(S,\,T,\,F)\), named a redistribution graph. In \(G\), set \(S\) represents processor set containing a source to send data, and set \(T\) represents processor set containing a destination to receive the data, and each edge in \(F\) indicates the message. The interested data redistributions are modeled as the following graph problems in this work. **Definition 1**. : _For a bipartite graph \(G=(S,\,T,\,F)\) as an input, the maximum edge coloring problem (MECP) is to find a set of edge colorings (partitions) {\(F_{1},\,F_{2},\,F_{3},\,\ldots,\,F_{z}\)} of \(F\) to minimize \(\sum_{i=1}^{z}\max\{w(e)|e\in F_{i}\}\), where w(e) is the weight of edge \(e\)._  
When a set of independent edges of the given graph \(G\) is used to represent a set of synchronized contention-free communications in MECP, the value \(max\{w(e)|e\in F_{i}\}\) indicates the longest time required to complete all communications allocated to \(i\)th step. Accordingly, the sum of \(max\{w(e)|e\in F_{i}\}\)(for \(1\leq i\leq z\)) is denoted as \(\sum_{i=1}^{z}\max\{w(e)|e\in F_{i}\}\), which indicates the overall communication time for the data redistribution represented by \(G\). In the next problem, we try to not only shorten the overall communication time but also the number of required communication steps. Additional variants of MECP use the minimum number of edge colorings, which are defined as follows. Figure 4: The distribution graph \(G_{GB(4,\,4)}\) of \(GB(4,\,4)\) in Figure 3.  
Figure 3: An example for \(GB(4,\,4)\). Definition 2: For a bipartite graph \(G=(S,\,T,\,F)\) as an input, the maximum degree edge coloring problem (MDECP) is to find out a set of edge colorings \(\{F_{1},F_{2},F_{3},\,\ldots,\,F_{\Delta(G)}\}\) of \(G\) to minimize \(\sum_{i=1}^{\Delta(G)}max[w(e)]e\in F_{i}\), where w(e) denotes the weight of e and \(\Delta(G)\) denotes the maximum degree of \(G\). For example, when the input is the distribution graph \(G\) in Figure 4, a solution to the MECP is the edge partition \(\{\{P_{\alpha},Q_{0}\},\,\{P_{1},Q_{1}\},\,\{P_{3},\,Q_{2}\}\},\{\{P_{\alpha},Q _{1}\},\,\{P_{2},Q_{2}\},\,\{P_{3},\,Q_{3}\}\}\), and \(\{\{P_{1},\,Q_{1}\}\}\) with the minimum value \(max[15,\,16,\,25]+max[9,\,15,\,11]+max[9]=25+15+9=49\), as shown in Figure 5. Since the number of colors used equals to the maximum degree of \(G\), the edge partition is also a solution to the MDECP. In previous research, the maximum coloring problem has been defined in [11; 12]. The problem here is finding a proper coloring on the vertex set of input graphs such that the color classes (disjoint vertex sets) \(V_{1}\), \(V_{2}\), \(\ldots\), \(V_{k}\) minimize \(\sum_{i=1}^{k}\max\{w(e)|e\in V_{i}\) \(\}\) where \(w\) denotes the weight function and \(k\) denotes the number of colors used.