# New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling
## 4 Two-Approximation Algorithm for Irregular Data Redistribution Scheduling
On the other hand, When \(\chi(v_{1})<\chi(v_{2})<\chi(u)\), the interval \([\chi(v_{1})-0.1,\chi(u)+0.1]\) (representing \(e_{1}\)) also intersects the interval \([\chi(v_{2})-0.1,\chi(u)+0.1]\) (representing \(e_{2}\)). When \(\chi(v_{1})<\chi(u)<\chi(v_{2})\), the interval \([\chi(v_{1})-0.1,\chi(u)+0.1]\) (representing \(e_{1}\)) intersects the interval \([\chi(u)-0.1,\chi(v_{2})+0.1]\) (representing \(e_{2}\)). Conversely, without loss of generality, when \(\chi(u_{1})\leq\chi(u_{2})\leq\chi(v_{1})\leq\chi(v_{2})\) and \(\{u_{1},\,u_{2}\}\subseteq S\) and \(\{v_{1},\,v_{2}\}\subseteq T\), we have a pair of overlapped intervals \([\chi(u_{1})-0.1,\chi(v_{1})+0.1]\) and \([\chi(u_{2})-0.1,\chi(v_{2})+0.1]\). We claim that the corresponding two edges \((u_{1},\,v_{1})\) and \((u_{2},\,v_{2})\) are incident with a same vertex (either \(u_{1}=u_{2}\) or \(v_{1}=v_{2}\)). Otherwise, we have \(u_{1}\
eq u_{2}\) and \(v_{1}\
eq v_{2}\) (similarly \(\chi(u_{1})\
eq\chi(u_{2})\) and \(\chi(v_{1})\
eq\chi(v_{2})\)), and the constructed intervals for the edges must be \([\chi(u_{1})-0.1,\chi(v_{1})+0.1]\) and \([\chi(u_{2})-0.1,\chi(v_{2})+0.1]\) where \(\chi(u_{1})<\chi(u_{2})<\chi(v_{1})<\chi(v_{2})\). Since \(\chi(u_{1})\) and \(\chi(v_{1})\) (similarly \(\chi(u_{2})\) and \(\chi(v_{2})\)) are in the same subintervals selected from \([1,\chi(v_{b0})]\), \([\chi(v_{b0}),\chi(v_{b1})]\),..., \([\chi(|_{|B|-1}),|S|+|T|]\). That means \(\chi(u_{1})\), \(\chi(u_{2})\), \(\chi(v_{1})\), \(\chi(v_{2})\) are in the same subintervals selected from \([1,\chi(v_{b0})]\), \([\chi(v_{b0}),\chi(v_{b1})]\),..., \([\chi(v_{|B|-1}),|S|+|T|]\). As a result, at most one vertex of \(\{u_{1},\,u_{2},\,v_{1},\,v_{2}\}\) is in \(B\). Otherwise, if \(u_{1}\) and \(v_{2}\) are in \(B\), then \(v_{1}\) and \(u_{2}\) should be adjacent to the same vertex. A contradiction occurs. Suppose only one vertex of \([u_{1},\,u_{2},\,v_{1},\,v_{2}]\) is in \(B\), the remaining two leaf vertices should be adjacent to a same node in \(B\). Another contradiction occurs. When \(\chi(u_{2})<\chi(u_{1})<\chi(v_{1})<\chi(v_{2})\), Without loss of generality, we have \(\{u_{1},\,u_{2},\,v_{1},\,v_{2}\}\). Figure 9: A redistribution graph \(G\) with the intervals of \(L(G)\). \(u_{2}\)]\(\subseteq\)\(S\) and \(\{v_{1},v_{2}\}\)\(\subseteq\)\(T\). Then two edges (\(u_{1}\), \(v_{1}\)) and (\(u_{2}\), \(v_{2}\)) are crossing in the biplanar graph drawing. A contradiction occurs. At last, the constructed interval model represents \(L(G)\), and finally we prove that the line graph of a communication graph of GEN-BLOCK data redistribution is an interval graph. We devise an approximation algorithm for maximum edge coloring problem (called AMECP) listed below. ```
Input: \(G=\)(\(X\), \(Y\), \(E\)) of GEN-BLOCK. Output: an edge coloring \(\{F_{1},F_{2},F_{3},\ldots,F_{2}\}\) of \(G\) and \(\sum_{i=1}^{k}max\{w(e)|e\in F_{i}\}\). 1: Construct \(L(G)\) from \(G\). 2: Find out an interval representation for \(L(G)\) by executing the recognition algorithm of interval graphs based on Theorem 4. 3: Construct a vertex coloring \(\{V_{1},V_{2},V_{3},\ldots,V_{2}\}\) of \(L(G)\) by executing an algorithm to solve the maximum coloring problem for interval graphs. 4: Construct an edge coloring \(\{F_{1},F_{2},F_{3},\ldots,F_{2}\}\) of \(G\) from vertex coloring \(\{V_{1},V_{2},V_{3},\ldots,V_{2}\}\), and calculate \(\sum_{i=1}^{2}max\{w(e)|e\in F_{i}\}\). ```  
**Algorithm** AMECP:  
The correctness and time complexity of AMECP are discussed and provided in Theorems 5 and 6. Theorem 5: _AMECP is an approximation algorithm with a ratio bound of two for MECP when the input is a biplanar graph._  
Proof: Because an edge coloring of \(G\) is always mapped to a vertex coloring of \(L(G)\), the MECP of \(G\) is converted to the maximum coloring problem of \(L(G)\) according to the mapping. Due to the fact that \(L(G)\) is an interval graph (proved in Theorem 4), an approximation algorithm with a ratio bound of two for MECP of \(G\) can be devised by executing [PERSON] et al.