《计算机基础》课程教学资源（参考论文）Comments on “the 1993 DIMACS Graph Coloring Challenge” and “Energy Function-Based Approaches to Graph Coloring”

TNN04-L105R Comments on the 1993 DIMACS Graph Coloring Challenge"and "Energy Function-Based Approaches to Graph Coloring" Jing Liu,Weicai Zhong,and Licheng Jiao,Senior Member,IEEE The problems in the first class are right,whereas those in the Abstract-Since all graphs in the 1993 DIMACS graph coloring two other classes may cause confusion.Table I gives the class challenge are undirected,each edge should be only counted once. of each problem.For the problems in the second class,the But in some files each edge is counted once,whereas in others each number of edges in the problem line should be divided by 2. edge is counted twice.So a systematical check on the DIMACS challenge is made to eliminate the inconsistencies.Besides,the and the edge lines should be let as they are.For the problems in experimental results of [2]counted each violated edges twice and the third class,the number of edges in the problem line should neglected the inconsistencies in the DIMACS challenge.So the be also divided by 2,and one of the two edge lines correct experimental results of 2 are also given. corresponding to the same edge should be deleted. For the files in the compressed format,the problem lines are Index Terms-Graph coloring,DIMACS challenge the same as those of the corresponding files in the DIMACS standard format,and the lower triangular part of the vertex-vertex adjacency matrix of the graph is given.So their I.INCONSISTENCIES IN THE 1993 DIMACS GRAPH COLORING inconsistencies can be corrected according to the above CHALLENGE paragraph. THE 1993 DIMACS graph coloring challenge [1]has been widely used in testing various new approaches for graph coloring problems.Since all graphs in the DIMACS challenge II.INCONSISTENT EXPERIMENTAL RESULTS OF [2] are undirected,each edge should be only counted once.But in The experiments of [2]used some graphs from the 1993 some files each edge is counted once,whereas in others each DIMACS graph coloring challenge.The authors of [2] edge is counted twice.These inconsistencies have affected neglected the inconsistencies pointed out in Section I,and many experimental results,and made many comparisons unfair. counted each violated edge twice in the coloring results.As a In what follows,a systematical check on the DIMACS result,the experimental results for the spanning subgraph challenge is made to eliminate the inconsistencies. Presently,the DIMACS challenge has 79 problems.They are k-coloring(SSC)problems in Table I of [2]are inconsistent.It brings difficulties for the other researches that want to make a given in two formats,namely,the DIMACS standard format comparison with [21.The correct results are given in Table II. and the compressed format.A translator is also given to go between the two formats.Each file in the DIMACS standard format has a problem line beginning with the letter p'.This ACKNOWLEDGMENT line gives the number of nodes and the number of edges of the graph.Following the problem line,each edge is given by a line The authors thank Andrea Di Blas,the first author of [2],for beginning with the letter 'e'.The inconsistencies lie between confirming both facts and for related discussions. the problem line and the edge lines.According to the current cases,the 79 problems can be divided into 3 classes: 1)The problem line counts each edge once,and each edge REFERENCES forms one edge line; [1]Website..[Online].Available:http://dimacs.rutgers.edu and 2)The problem line counts each edge twice,and each edge http://mat.esia.cmu.edu/COLOR/color.html [2]A.D.Blas,A.Jagota,and R.Hughey,"Energy Function-Based forms one edge line: Approaches to Graph Coloring,"IEEE Trans.Neural Networks,vol.13, 3)The problem line counts each edge twice,and each edge n0.1,Pp.81-91,2002. forms two edge lines; Manuscript received March 27,2004. The authors are with the Institute of Intelligent Information Processing, Xidian University,Xi'an,710071,China Weicai Zhong,corresponding author,phone:0086-029-88202661;fax: 0086-029-88201023;e-mail:neouma@mail.xidian.edu.cn

TNN04-L105R 1 Abstract—Since all graphs in the 1993 DIMACS graph coloring challenge are undirected, each edge should be only counted once. But in some files each edge is counted once, whereas in others each edge is counted twice. So a systematical check on the DIMACS challenge is made to eliminate the inconsistencies. Besides, the experimental results of [2] counted each violated edges twice and neglected the inconsistencies in the DIMACS challenge. So the correct experimental results of [2] are also given. Index Terms—Graph coloring, DIMACS challenge I. INCONSISTENCIES IN THE 1993 DIMACS GRAPH COLORING CHALLENGE HE 1993 DIMACS graph coloring challenge [1] has been widely used in testing various new approaches for graph coloring problems. Since all graphs in the DIMACS challenge are undirected, each edge should be only counted once. But in some files each edge is counted once, whereas in others each edge is counted twice. These inconsistencies have affected many experimental results, and made many comparisons unfair. In what follows, a systematical check on the DIMACS challenge is made to eliminate the inconsistencies. Presently, the DIMACS challenge has 79 problems. They are given in two formats, namely, the DIMACS standard format and the compressed format. A translator is also given to go between the two formats. Each file in the DIMACS standard format has a problem line beginning with the letter ‘p’. This line gives the number of nodes and the number of edges of the graph. Following the problem line, each edge is given by a line beginning with the letter ‘e’. The inconsistencies lie between the problem line and the edge lines. According to the current cases, the 79 problems can be divided into 3 classes: 1) The problem line counts each edge once, and each edge forms one edge line; 2) The problem line counts each edge twice, and each edge forms one edge line; 3) The problem line counts each edge twice, and each edge forms two edge lines; Manuscript received March 27, 2004. The authors are with the Institute of Intelligent Information Processing, Xidian University, Xi’an, 710071, China Weicai Zhong, corresponding author, phone: 0086-029-88202661; fax: 0086-029-88201023; e-mail: neouma@mail.xidian.edu.cn. The problems in the first class are right, whereas those in the two other classes may cause confusion. Table I gives the class of each problem. For the problems in the second class, the number of edges in the problem line should be divided by 2, and the edge lines should be let as they are. For the problems in the third class, the number of edges in the problem line should be also divided by 2, and one of the two edge lines corresponding to the same edge should be deleted. For the files in the compressed format, the problem lines are the same as those of the corresponding files in the DIMACS standard format, and the lower triangular part of the vertex-vertex adjacency matrix of the graph is given. So their inconsistencies can be corrected according to the above paragraph. II. INCONSISTENT EXPERIMENTAL RESULTS OF [2] The experiments of [2] used some graphs from the 1993 DIMACS graph coloring challenge. The authors of [2] neglected the inconsistencies pointed out in Section I, and counted each violated edge twice in the coloring results. As a result, the experimental results for the spanning subgraph k-coloring (SSC) problems in Table I of [2] are inconsistent. It brings difficulties for the other researches that want to make a comparison with [2]. The correct results are given in Table II. ACKNOWLEDGMENT The authors thank Andrea Di Blas, the first author of [2], for confirming both facts and for related discussions. REFERENCES [1] Website.. [Online]. Available: http://dimacs.rutgers.edu and http://mat.gsia.cmu.edu/COLOR/color.html [2] A. D. Blas, A. Jagota, and R. Hughey, “Energy Function-Based Approaches to Graph Coloring,” IEEE Trans. Neural Networks, vol. 13, no. 1, pp.81-91, 2002. Comments on “the 1993 DIMACS Graph Coloring Challenge” and “Energy Function-Based Approaches to Graph Coloring” Jing Liu, Weicai Zhong, and Licheng Jiao, Senior Member, IEEE T

TNN04-L105R TABLEI THE CLASS OF EACH GRAPH IN THE 1993 DIMACS GRAPH COLORING CHALLENGE Names Classes Names Classes Names Classes Names Classes DSJC1000.1 (2) t1at300280 (1) mulsol i.I (1) miles750 3) DSJC1000.5 (2) fpsol2.i.1 (1) mulsol i.2 (1) queen10 10 (3) DSJC1000.9 (2) fpsol2.1.2 1) mulsol i.3 (1) queenl1 11 (3) DSJC125.1 (2) fpsol2.i.3 (1) mulsol i.4 (1) queen12 12 (3) DSJC125.5 (2) inithxi.I (1) mulsol i.5 (1) queen13_13 (3) DSJC125.9 (2) inithx.i.2 (1) schooll (1) queen14 14 (3) DSJC250.1 (2) inithx.i.3 (1) schooll nsh (1) queen15 15 (3) DSJC250.5 (2) latin_square 10 1) zeroin.i.I (1) queen1616 (3) DSJC250.9 (2) le45015a (1) zeroin.i.2 (1) queen5 5 (3) DSJC500.1 (2) 1e45015b 1) Zeroin.1.3 (1) queen6 6 (3) DSJC500.5 (2) le45015c (1) anna (3) queen7_7 (3) DSJC500.9 (2) le45015d 1) david (3) queen8 12 (3) DSJR500.1 (2) le45025a (1) homer (3) queen8 8 (3) DSJR500.1c (2) 1e45025b (1) huck (3) queen9 9 (3) DSJR500.5 (2) 1e45025c (1) jean (3) myciel3 (1) f1at1000_50_0 (1) 1e45025d (1) games120 (3) myciel4 1) flat1000_600 (1) le450 5a 1) miles1000 (3) myciel5 1) f1at1000760 (1) 1e4505b (1) miles1500 (3) myciel6 (1) f1lat300200 (1) le450 5c (1) miles250 (3) myciel7 (1) f1lat300260 (1) le450 5d (1) miles500 (3) TABLE II THE CORRECT EXPERIMENTAL RESULTS FOR SSC IN [2] Name ME vN Name M-E V viNo DSJC1000.1 49629 220.9 0.45 le45015a 8168 64.1 0.78 DSJC1000.5 249826 369.2 0.15 le450_15c 16680 283.9 1.70 DSJC1000.9 449449 3019 0.07 le45025a 8260 11.7 0.14 DSJC250.1 3218 45.9 1.43 le45025c 17343 94.0 0.54 DSJC250.5 15668 70.2 0.45 le450_5a 5714 292.0 5.11 DSJC250.9 27897 50.8 0.18 le450 5c 9803 40.4 0.41 DSJC500.1 12458 120.7 0.97 miles1500 5198 2.2 0.04 DSJC500.5 62624 160.3 0.26 miles250 387 0.9 0.23 DSJC500.9 112437 130.2 0.12 miles750 2116 2.8 013 DSJR500.1 3555 10.9 0.31 mulsol i.I 3925 1.8 0.05 DSR500.5 58862 57.2 0.10 myciel5 236 0.0 0.00 f1at1000500 245000 1483.5 0.61 myciel6 755 0.2 0.03 f1at1000760 246708 499.5 0.20 myciel7 2360 0.4 0.02 f1at300200 21375 306.6 1.43 queen13 13 3328 44.2 1.33 f1at300280 21 695 125.2 0.58 queen14 14 4186 83 0.20 fpsol2.i.1 11654 9.7 0.08 queen15 15 5180 27.2 0.53 fpsol2.i.2 8691 22.8 0.26 queen16 16 6320 31.6 0.50 inithx.i.I 18707 22.1 0.12 schooll 19095 59.9 0.31 inithx.i.2 13979 37.6 0.27 zeroin.i.I 4100 4.8 012

TNN04-L105R 2 TABLE I THE CLASS OF EACH GRAPH IN THE 1993 DIMACS GRAPH COLORING CHALLENGE TABLE II THE CORRECT EXPERIMENTAL RESULTS FOR SSC IN [2]

TNN04-L105R 3 Jing Liu was born in Xi'an,China,on Mar.5, 1977.She received the B.S.degree in computer science and technology from Xidian University. Xi'an,China,in 2000,and received the Ph.D. degree in circuits and systems from the Institute of Intelligent Information Processing of Xidian University in 2004.Now she is a teacher in Xidian University. Her research interests include evolutionary computation,multiagent systems,and data mining. Weicai Zhong was born in Jiangxi,China,on Sept 26,1977.He received the B.S.degree in computer science and technology from Xidian University Xi'an,China,in 2000,and received the Ph.D. degree in pattern recognition and intelligent system from the Institute of Intelligent Information Processing of Xidian University in 2004.Now he is a Postdoctoral Fellow in Xidian University. His research interests include evolutionary computation,multiagent systems,,and data mining. Licheng Jiao(SM'89)was born in Shaanxi,China, on Oct.15,1959.He received the B.S.degree from Shanghai Jiaotong University,Shanghai,China,in 1982.He received the M.S.and Ph.D.degrees from Xi'an Jiaotong University,Xi'an,China,in 1984 and 1990,respectively. From 1984 to 1986,he was an Assistant Professor in Civil Aviation Institute of China, Tianjing,China.During 1990 and 1991,he was a Postdoctoral Fellow in the National Key Lab for Radar Signal Processing,Xidian University,Xi'an China.Now he is the Dean of the electronic engineering school and the director of the Institute of Intelligent Information Processing of Xidian University.His current research interests include signal and image processing.nonlinear circuit and systems theory,learning theory and algorithms,optimization problems, wavelet theory,and data mining.He is the author of there books:Theory of Neural Network Systems(Xi'an,China:Xidian Univ.Press,1990),Theory and Application on Nonlinear Transformation Functions (Xi'an,China:Xidian Univ.Press,1992),and Applications and Implementations of Neural Networks (Xi'an,China:Xidian Univ.Press,1996).He is the author or coauthor of more than 150 scientific papers

TNN04-L105R 3 Jing Liu was born in Xi’an, China, on Mar. 5, 1977. She received the B.S. degree in computer science and technology from Xidian University, Xi’an, China, in 2000, and received the Ph.D. degree in circuits and systems from the Institute of Intelligent Information Processing of Xidian University in 2004. Now she is a teacher in Xidian University. Her research interests include evolutionary computation, multiagent systems, and data mining. Weicai Zhong was born in Jiangxi, China, on Sept. 26, 1977. He received the B.S. degree in computer science and technology from Xidian University, Xi’an, China, in 2000, and received the Ph.D. degree in pattern recognition and intelligent system from the Institute of Intelligent Information Processing of Xidian University in 2004. Now he is a Postdoctoral Fellow in Xidian University. His research interests include evolutionary computation, multiagent systems, , and data mining. Licheng Jiao (SM’89) was born in Shaanxi, China, on Oct. 15, 1959. He received the B.S. degree from Shanghai Jiaotong University, Shanghai, China, in 1982. He received the M.S. and Ph.D. degrees from Xi’an Jiaotong University, Xi’an, China, in 1984 and 1990, respectively. From 1984 to 1986, he was an Assistant Professor in Civil Aviation Institute of China, Tianjing, China. During 1990 and 1991, he was a Postdoctoral Fellow in the National Key Lab for Radar Signal Processing, Xidian University, Xi’an, China. Now he is the Dean of the electronic engineering school and the director of the Institute of Intelligent Information Processing of Xidian University. His current research interests include signal and image processing, nonlinear circuit and systems theory, learning theory and algorithms, optimization problems, wavelet theory, and data mining. He is the author of there books: Theory of Neural Network Systems (Xi’an, China: Xidian Univ. Press, 1990), Theory and Application on Nonlinear Transformation Functions (Xi’an, China: Xidian Univ. Press, 1992), and Applications and Implementations of Neural Networks (Xi’an, China: Xidian Univ. Press, 1996). He is the author or coauthor of more than 150 scientific papers