{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T21:18:35Z","timestamp":1790630315232,"version":"4.1.0"},"reference-count":35,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T00:00:00Z","timestamp":1563235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["106-2221-E-216 -004"],"award-info":[{"award-number":["106-2221-E-216 -004"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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 \u201cmaximum edge coloring problem\u201d, the \u201cmaximum degree edge coloring problem\u201d, and the \u201ccost-sharing maximum edge coloring problem\u201d 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 \u201ccost-sharing maximum edge coloring problem\u201d is an NP-complete problem even when the input graph is biplanar.<\/jats:p>","DOI":"10.3390\/a12070142","type":"journal-article","created":{"date-parts":[[2019,7,17]],"date-time":"2019-07-17T02:44:03Z","timestamp":1563331443000},"page":"142","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling"],"prefix":"10.3390","volume":"12","author":[{"given":"Qinghai","family":"Li","sequence":"first","affiliation":[{"name":"Department of Electronic Engineering, Zhejiang Industry and Trade Vocational College, East Road 717, Wenzhou 325003, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7783-1513","authenticated-orcid":false,"given":"Chang Wu","family":"Yu","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, Chung Hua University, No.707, Sec.2, WuFu Road, Hsinchu 30012, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,7,16]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1217","DOI":"10.1109\/71.819945","article-title":"Efficient Algorithms for Block-Cyclic Data Redistribution Between Processor Sets","volume":"10","author":"Park","year":"1999","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_2","first-page":"1201","article-title":"Algorithmic Redistribution Methods for Block-Cyclic Decompositions","volume":"10","author":"Petitet","year":"1999","journal-title":"IEEE Trans. PDS"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1023\/B:SUPE.0000026848.34971.27","article-title":"Divide-and-conquer Algorithm for Irregular Redistributions in Parallelizing Compilers","volume":"29","author":"Wang","year":"2004","journal-title":"J. Supercomput."},{"key":"ref_4","first-page":"76","article-title":"An Efficient Algorithm for Irregular Redistribution in Parallelizing Compilers","volume":"Volume 2745","author":"Wang","year":"2003","journal-title":"Lecture Notes in Computer Science, Proceedings of 2003 International Symposium on Parallel and Distributed Processing with Applications, Aizu-Wakamatsu, Japan, 2\u20134 July, 2003"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Tang, B., Jaggi, N., Wu, H., and Kurkal, R. (2010, January 8\u201312). Energy-efficient data redistribution in sensor network. Proceedings of the 7th IEEE International Conference on Mobile Ad-hoc and Sensor Systems, San Francisco, CA, USA.","DOI":"10.1109\/MASS.2010.5664029"},{"key":"ref_6","unstructured":"Yi, Q., Wang, J., and Liu, C. (2015, January 15\u201317). Energy-efficient data storage solutions under sink failures. Proceedings of the 10th International Conference on Communications and Networking in China, Shanghai, China."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Cheng, L., and Li, T. (2016, January 19\u201322). Efficient data redistribution to speed up big data analytics in large systems. Proceedings of the 2016 IEEE 23rd International Conference on High Performance Computing, Hyderabad, India.","DOI":"10.1109\/HiPC.2016.020"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Dreher, M., and Peterka, T. (2016, January 12\u201316). Bredala: Semantic data redistribution for in situ applications. Proceedings of the 2016 IEEE International Conference on Cluster Computing, Taipei, Taiwan.","DOI":"10.1109\/CLUSTER.2016.30"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Marrinan, T., Insley, J.A., Rizzi, S., Tessier, F., and Papka, M.E. (June, January 29). Automated dynamic data redistribution. Proceedings of the 2017 IEEE International Parallel and Distributed Processing Symposium Workshops, Lake Buena Vista, FL, USA.","DOI":"10.1109\/IPDPSW.2017.17"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Cheng, L., Wang, Y., Pei, Y., and Epema, D. (2017, January 14\u201317). A Coflow-Based Co-Optimization Framework for High-Performance Data Analytics. Proceedings of the 2017 46th International Conference on Parallel Processing (ICPP), Bristol, UK.","DOI":"10.1109\/ICPP.2017.48"},{"key":"ref_11","unstructured":"Pemmaraju, S.V., Raman, R., and Varadarajan, K.R. (2004, January 11\u201314). Buffer minimization using max-coloring. Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, USA."},{"key":"ref_12","first-page":"1064","article-title":"Approximation algorithms for the max-coloring problem","volume":"Volume 3580","author":"Pemmaraju","year":"2015","journal-title":"Lecture Notes in Computer Science, Proceedings of the International Colloquium on Automata, Languages, and Programming, Lisbon, Portugal, 11\u201315 July 2005"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1145\/321978.321985","article-title":"Open shop scheduling to minimize finish time","volume":"23","author":"Gonzales","year":"1976","journal-title":"J. ACM"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1023\/A:1015313917431","article-title":"Scheduling GEN_BLOCK Array Redistribution","volume":"2","author":"Yook","year":"2002","journal-title":"J. Supercomput."},{"key":"ref_15","first-page":"295","article-title":"Irregular Redistribution Scheduling by partitioning Messages","volume":"Volume 3740","author":"Yu","year":"2005","journal-title":"Lecture Notes in Computer Science, Proceedings of the 10th Asia-Pacific Computer Systems Architecture Conference, Singapore, 24\u201326 October 2005"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/S0020-0255(00)00048-7","article-title":"On the complexity of the maximum biplanar subgraph problem","volume":"129","author":"Yu","year":"2000","journal-title":"Inf. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0304-3975(94)00220-D","article-title":"Efficient parallel algorithms for doubly convex-bipartite graphs","volume":"147","author":"Yu","year":"1995","journal-title":"Theor. Computer Sci."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., and Murty, U.S.R. (1976). Graph Theory with Applications, Macmillan.","DOI":"10.1007\/978-1-349-03521-2"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1006\/jpdc.1996.0142","article-title":"Optimization for Efficient Data redistribution on Distributed Memory Multicomputers","volume":"38","author":"Ramaswamy","year":"1996","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1006\/jpdc.1997.1351","article-title":"Fast runtime block cyclic data redistribution on multiprocessors","volume":"45","author":"Prylli","year":"1997","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_21","unstructured":"Bandera, G., and Zapata, E.L. (1999, January 12\u201316). Sparse Matrix Block-Cyclic Redistribution. Proceedings of the Proceedings 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing, San Juan, PR, USA."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1201","DOI":"10.1109\/71.895789","article-title":"A Generalized Basic-Cycle Calculation Method for Efficient Array Redistribution","volume":"11","author":"Hsu","year":"2000","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"743","DOI":"10.1109\/71.940748","article-title":"A Generalized Processor Mapping Technique for Array Redistribution","volume":"12","author":"Hsu","year":"2001","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1234","DOI":"10.1109\/71.476166","article-title":"Processor Mapping Technique Toward Efficient Data Redistribution","volume":"6","author":"Kalns","year":"1995","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_25","unstructured":"Lee, S., Yook, H., Koo, M., and Park, M. (, January March). Processor reordering algorithms toward efficient GEN_BLOCK redistribution. Proceedings of the ACM Symposium on Applied Computing, Las Vegas, NV, USA."},{"key":"ref_26","unstructured":"Kaushik, S.D., Huang, C.H., Ramanujam, J., and Sadayappan, P. (1995, January 25\u201328). Multiphase data redistribution: Modeling and evaluation. Proceedings of the 9th International Parallel Processing Symposium, Santa Barbara, CA, USA."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1109\/71.663945","article-title":"Scheduling Block-Cyclic Data redistribution","volume":"9","author":"Desprez","year":"1998","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1325","DOI":"10.1016\/S0167-8191(00)00027-2","article-title":"Contention-Free Communication Scheduling for Array Redistribution","volume":"26","author":"Guo","year":"2000","journal-title":"Parallel Comput."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1007\/PL00008265","article-title":"Efficient Algorithms for Block-Cyclic Redistribution of Arrays","volume":"24","author":"Lim","year":"1999","journal-title":"Algorithmica"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1485","DOI":"10.1016\/0167-8191(95)00027-L","article-title":"Optimization of Data redistribution for Distributed Memory Multicomputers. short communication","volume":"21","author":"Wakatani","year":"1995","journal-title":"Parallel Comput."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1023\/A:1024262610201","article-title":"Symbolic Communication Set Generation for Irregular Parallel Applications","volume":"25","author":"Guo","year":"2003","journal-title":"J. Supercomput."},{"key":"ref_32","unstructured":"Eades, P., McKay, B.D., and Wormald, N.C. (2019, May 15). On an edge crossing problem. Available online: http:\/\/users.cecs.anu.edu.au\/~bdm\/papers\/EdgeCrossing.pdf."},{"key":"ref_33","first-page":"1","article-title":"On planarization algorithms of 2-level graphs","volume":"38","author":"Tomii","year":"1977","journal-title":"Tech. Group. Elect. Comp. IECEJ"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","article-title":"Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms","volume":"13","author":"Booth","year":"1976","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_35","unstructured":"Garey, M.R., and Johnson, D.S. (1978). Computers and Intractability: A guide to the Theory of NP-completeness, Freeman."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/7\/142\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:06:20Z","timestamp":1760187980000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/7\/142"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,16]]},"references-count":35,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2019,7]]}},"alternative-id":["a12070142"],"URL":"https:\/\/doi.org\/10.3390\/a12070142","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,16]]}}}