[40] H.J. Karloff and D B. Shmoys, Efficient parallel algorithms for edge coloring problems. J Algorithms 8(1987), 39-52 41 W. Liang, Fast parallel algorithms for the approximate edge-coloring problem. Inform Process.len:.56(1995),333-338 42]W. Liang, X. Shen and Q. Hu, Parallel algorithms for the edge-coloring and edge-coloring update problems. J. Parallel Distrib. Comput. 32(1996), 66-73 43]R. Motwani, J. Naor and M. Naor, The probabilistic method yields deterministic parallel algorithms. J. Comput. System Sci. 49(1994), 478-516 [ 44]D. Bertsimas, C-P. Teo, andR. Vohra, On dependent randomized rounding algorithms, Proc 5th Int. Conf. on Integer Prog. and Combinatorial Optimization, Lecture Notes in Comput. Sci 084, Springer-Verlag, (1996), 330-344 45 M K. Goldberg, Edge-colorings of multigraphs: recoloring technique, J. Graph Theory 8(1984),123-127 [46]DS. Hochbaum, T. Nishizeki and D B. Shmoys, Better than"Best Possible"algorithm to edge color multi graphs, Journal of AlgorithmS, 7(1986), 79-104 [47 T. Nishizeki and K. Kashiwagi, On the 1. I edge-coloring of multigraphs, SIAMJ. Disc Mamh,3(1990),391-410 [48]J. Kahn, Asymptotics of the chromatic index for multigraphs, Journal of Combinatorial Theory(SerB),68(1996),233-254 [49]x. Zhou H. Susuki, and T. Nishizeki, A linear algorithm for edge-coloring series-parallel multigraphs, J. Algorithms, 20(1996), 174-201 50]X. Zhou H. Susuki, and T. Nishizeki, An NC parallel algorithm for edge-coloring series-parallel multigraphs, J. Algorithms, 23(1997), 359-374 51]B Berger and J Rompel, Simulating(log n-wise independence in NC. J. ACM 38(1991), 026-1046 3.求二部图G=(X,Y)的边正常△(G)染色的算法 ●算法思想:给G添加必要的顶点使得|XHY,再添加必要的边使得G成为△(G)正 则二部图,所得图记为G,然后反复运用匈牙利算法求G的完美匹配。由第3章Knig 定理,G存在完美匹配。每求出G的一个完美匹配,便可用一种颜色给这个完美匹 配的边染色。因为共可求得G的△(G)个边不重的完美匹配,故可得G(从而G)的 边正常△(G)染色 二部图边染色算法:求二部图的边正常△(G)染色(求二部图的△(G)个边不交的匹配)。 输入:二部图G=(X,Y) 输出:G的边正常△G)染色(△(G)个边不交的匹配) 第0步:添加顶点使得X=Y1,所得图记为G 第1步:若Δ(G)=δ(G),令k=1,转第3步;否则,转第2步。2 [40] H.J. Karloff and D.B. Shmoys, Efficient parallel algorithms for edge coloring problems. J. Algorithms 8 (1987), 39–52. [41] W. Liang, Fast parallel algorithms for the approximate edge-coloring problem. Inform. Process. Lett. 56 (1995), 333–338. [42] W. Liang, X. Shen and Q. Hu, Parallel algorithms for the edge-coloring and edge-coloring update problems. J. Parallel Distrib. Comput. 32 (1996), 66-73. [43] R. Motwani, J. Naor and M. Naor, The probabilistic method yields deterministic parallel algorithms. J. Comput. System Sci. 49 (1994), 478-516. [44] D. Bertsimas, C-P. Teo, and R. Vohra, On dependent randomized rounding algorithms, Proc. 5th Int. Conf. on Integer Prog. and Combinatorial Optimization, Lecture Notes in Comput. Sci. 1084, Springer-Verlag, (1996), 330-344. [45] M.K. Goldberg, Edge-colorings of multigraphs: recoloring technique, J. Graph Theory, 8(1984), 123-127. [46] D.S. Hochbaum, T. Nishizeki and D.B. Shmoys, Better than “Best Possible” algorithm to edge color multi graphs, Journal of Algorithms, 7(1986), 79-104 [47] T. Nishizeki and K. Kashiwagi, On the 1.1 edge-coloring of multigraphs, SIAM J. Disc. Math. , 3(1990), 391-410. [48] J. Kahn, Asymptotics of the chromatic index for multigraphs, Journal of Combinatorial Theory (Ser. B), 68(1996), 233-254. [49] X. Zhou H. Susuki, and T. Nishizeki, A linear algorithm for edge-coloring series-parallel multigraphs, J. Algorithms, 20(1996), 174-201. [50] X. Zhou H. Susuki, and T. Nishizeki, An NC parallel algorithm for edge-coloring series-parallel multigraphs, J. Algorithms, 23(1997), 359-374. [51] B. Berger and J. Rompel, Simulating (logc n)-wise independence in NC. J. ACM 38 (1991), 1026–1046. 3. 求二部图G = (X ,Y ) 的边正常 Δ(G) 染色的算法 z 算法思想：给 G 添加必要的顶点使得| X |=|Y |，再添加必要的边使得 G 成为 Δ(G) 正 则二部图，所得图记为 * G ，然后反复运用匈牙利算法求 * G 的完美匹配。由第 3 章 König 定理， * G 存在完美匹配。每求出 * G 的一个完美匹配，便可用一种颜色给这个完美匹 配的边染色。因为共可求得 * G 的 Δ(G) 个边不重的完美匹配，故可得 * G （从而 G）的 边正常 Δ(G) 染色。 z 二部图边染色算法：求二部图的边正常 Δ(G) 染色(求二部图的 Δ(G) 个边不交的匹配)。 输入：二部图 G=(X,Y) 输出：G 的边正常 Δ(G) 染色（ Δ(G) 个边不交的匹配） 第 0 步：添加顶点使得|X|=|Y|，所得图记为 * G 。 第 1 步：若 ( ) ( ) * * Δ G = δ G ，令k = 1，转第 3 步；否则，转第 2 步