Table 1. Results on Standard Graphs for Different Heuristics for Vertex Ordering

Table 1. Results on standard graphs for different heuristics for vertex ordering

Graphs / n=|V| / rdfs / rbfs / rand / Vcover / maxNbr / F-value / p-value
K2,3 / 5 / Mean / 2 / 3 / 3 / 5 / 3 / 1146.459 / 0.000
Sd / 0.424264 / 0.972269 / 1.100835 / 0 / 0
Min / 1 / 1 / 1 / 5 / 3
K3,3 / 6 / Mean / 3 / 7 / 5 / 9 / 8 / 1922.481 / 0.000
Sd / 0 / 0 / 1.75383 / 0 / 0
Min / 3 / 7 / 3 / 9 / 8
K3,4 / 7 / Mean / 13 / 21 / 17 / 28 / 21 / 3450.339 / 0.000
Sd / 0.46291 / 3.119982 / 3.433092 / 0.887326 / 0.751597
Min / 12 / 15 / 12 / 26 / 18
K4,4 / 8 / Mean / 16 / 33 / 24 / 37 / 33 / 3362.339 / 0.000
Sd / 0 / 0 / 4.470356 / 0.844913 / 0.86685
Min / 16 / 33 / 17 / 33 / 30
K4,5 / 9 / Mean / 45 / 68 / 54 / 84 / 74 / 4453.506 / 0.000
Sd / 1.331563 / 10.08867 / 7.89275 / 0.534522 / 0.808122
Min / 43 / 44 / 43 / 82 / 70
K5,5 / 10 / Mean / 50 / 96 / 63 / 100 / 96 / 3783.965 / 0.000
Sd / 0 / 0 / 7.981202 / 0.798979 / 0.896478
Min / 50 / 96 / 50 / 96 / 93
K7,8 / 15 / Mean / 430 / 670 / 495 / 732 / 707 / 5702.035 / 0.000
Sd / 3.717361 / 54.90306 / 54.91072 / 93.61755 / 0.633745
Min / 426 / 473 / 433 / 712 / 704
K10,10 / 20 / Mean / 1200 / 2016 / 1328 / 2025 / 2017 / 5234.960 / 0.000
Sd / 0 / 0 / 89.95019 / 1.211509 / 0.746147
Min / 1200 / 2016 / 1224 / 2020 / 2014
K12,13 / 25 / Mean / 3660 / 5546 / 3924 / 5940 / 5863 / 6080.757 / 0.000
Sd / 11.3832 / 434.2428 / 162.3446 / 0.677631 / 0.682433
Min / 3651 / 3713 / 3688 / 5937 / 5860
K15,15 / 30 / Mean / 6825 / 11011 / 7389 / 11026 / 10615 / 5962.462 / 0.000
Sd / 0 / 0 / 394.1678 / 0.912722 / 1960.306
Min / 6825 / 11011 / 6927 / 11020 / 11009
K17,18 / 35 / Mean / 14571 / 22141 / 15353 / 23121 / 22967 / 6326.246 / 0.000
Sd / 30.29243 / 1440.035 / 530.5583 / 1.095631 / 1.277913
Min / 14506 / 15212 / 14767 / 23117 / 22960
K20,20 / 40 / Mean / 22800 / 36081 / 24195 / 36101 / 36082 / 6254.892 / 0.000
Sd / 0 / 0 / 858.1383 / 1.16689 / 1.226244
Min / 22800 / 36081 / 23216 / 36097 / 36077
K22,23 / 45 / Mean / 40530 / 60821 / 42355 / 63525 / 63273 / 6510.951 / 0.000
Sd / 38.12487 / 4250.623 / 1319.278 / 1.328034 / 0.833238
Min / 40502 / 42345 / 40936 / 63519 / 63270
K25,25 / 50 / Mean / 57500 / 89977 / 60125 / 90000 / 89977 / 6385.789 / 0.000
Sd / 0 / 3.394113 / 1424.902 / 0 / 3.595292
Min / 57500 / 89976 / 58200 / 90000 / 89970
K40,40 / 80 / Mean / 395200 / 608362 / 404855 / 608385.7 / 608362 / 119039.524 / 0.000
Sd / 0 / 5.515433 / 5231.376 / 71.69477 / 5.581895
Min / 395200 / 608361 / 397679 / 608037 / 608359
C4 / 4 / Mean / 0 / 0 / 1 / 1 / 0 / 104.693 / 0.000
Sd / 0 / 0 / 0.504672 / 0 / 0
Min / 0 / 0 / 0 / 1 / 0
C5 / 5 / Mean / 0 / 1 / 2 / 2 / 2 / 297.454 / 0.000
Sd / 0 / 0.503457 / 0.974156 / 0.416497 / 0.377424
Min / 0 / 0 / 0 / 0 / 0
C6 / 6 / Mean / 0 / 2 / 3 / 6 / 0 / 165.678 / 0.000
Sd / 0 / 0.498569 / 1.644409 / 0.543984 / 0
Min / 0 / 1 / 0 / 3 / 0
C7 / 6 / Mean / 0 / 3 / 4 / 7 / 2 / 287.207 / 0.000
Sd / 0 / 0.504672 / 1.909803 / 0.558423 / 0.373073
Min / 0 / 2 / 0 / 5 / 0
C8 / 6 / Mean / 0 / 4 / 6 / 16 / 3 / 240.739 / 0.000
Sd / 0 / 0.490314 / 2.412891 / 2.518179 / 0.755929
Min / 0 / 3 / 1 / 8 / 0
C9 / 6 / Mean / 0 / 5 / 9 / 16 / 5 / 322.927 / 0.000
Sd / 0 / 0.46291 / 3.976513 / 0.795138 / 0.469911
Min / 0 / 4 / 2 / 13 / 3
C10 / 6 / Mean / 0 / 6 / 10 / 29 / 6 / 236.320 / 0.000
Sd / 0 / 0.471212 / 4.026899 / 0.899887 / 0.532993
Min / 0 / 5 / 2 / 25 / 3
C15 / 15 / Mean / 0 / 11 / 25 / 67 / 8 / 204.395 / 0.000
Sd / 0 / 0.388088 / 7.515535 / 0.606092 / 0.754848
Min / 0 / 10 / 8 / 65 / 5
C20 / 20 / Mean / 0 / 16 / 55 / 154 / 11 / 169.664 / 0.000
Sd / 0 / 0.274048 / 13.01523 / 0.873417 / 0.934814
Min / 0 / 15 / 28 / 151 / 7
C25 / 25 / Mean / 0 / 21 / 85 / 233 / 16 / 165.650 / 0.000
Sd / 0 / 0.274048 / 16.60588 / 0.746147 / 0.698687
Min / 0 / 20 / 48 / 231 / 12
C30 / 30 / Mean / 0 / 26 / 133 / 378 / 18 / 151.798 / 0.000
Sd / 0 / 0.35051 / 20.64235 / 0.318799 / 0
Min / 0 / 25 / 90 / 376 / 18
C35 / 35 / Mean / 0 / 31 / 173 / 497 / 21 / 147.542 / 0.000
Sd / 0 / 0.303046 / 31.24615 / 0 / 0
Min / 0 / 30 / 117 / 497 / 21
C40 / 40 / Mean / 0 / 36 / 245 / 703 / 25 / 143.125 / 0.000
Sd / 0 / 0.328261 / 28.39158 / 0 / 0
Min / 0 / 35 / 199 / 703 / 25
C45 / 45 / Mean / 0 / 41 / 301 / 862 / 28 / 140.982 / 0.000
Sd / 0 / 0.274048 / 43.59686 / 0 / 0
Min / 0 / 40 / 203 / 862 / 28
C50 / 50 / Mean / 0 / 46 / 383 / 1128 / 31 / 135.940 / 0.000
Sd / 0 / 0.35051 / 60.34642 / 0 / 0
Min / 0 / 45 / 214 / 1128 / 31
Q2 / 4 / Mean / 0 / 0 / 1 / 2 / 1 / 80.801 / 0.000
Sd / 0 / 0 / 0.478518 / 0.377424 / 0.282843
Min / 0 / 0 / 0 / 0 / 0
Q3 / 8 / Mean / 5 / 14 / 12 / 25 / 14 / 997.150 / 0.000
Sd / 1.26168 / 0.504672 / 3.988197 / 0.558423 / 0.451754
Min / 3 / 13 / 5 / 22 / 12
Q4 / 16 / Mean / 60 / 150 / 128 / 272 / 122 / 1067.128 / 0.000
Sd / 8.058688 / 1.974945 / 21.84182 / 0.754848 / 0.66884
Min / 46 / 147 / 79 / 269 / 119
Q5 / 32 / Mean / 445 / 1080 / 944 / 2062 / 846 / 990.822 / 0.000
Sd / 51.64429 / 5.226502 / 95.32421 / 0.781417 / 0.428095
Min / 363 / 1072 / 729 / 2058 / 843
Q6 / 64 / Mean / 2988 / 6450 / 5759 / 13143 / 4725 / 902.875 / 0.000
Sd / 228.3757 / 18.60103 / 396.4267 / 0.977502 / 0.890081
Min / 2463 / 6419 / 4760 / 13139 / 4720
CC2 / 8 / Mean / 1 / 5 / 8 / 6 / 3 / 451.293 / 0.000
Sd / 0.503457 / 0.736511 / 3.398439 / 0 / 0
Min / 0 / 3 / 2 / 6 / 3
CC3 / 24 / Mean / 55 / 145 / 221 / 297 / 102 / 863.974 / 0.000
Sd / 14.49892 / 10.64676 / 34.22325 / 0.632778 / 0.707107
Min / 31 / 122 / 141 / 295 / 100
CC4 / 64 / Mean / 476 / 1440 / 1994 / 2789 / 913 / 861.719 / 0.000
Sd / 77.04534 / 84.9605 / 189.3761 / 0.807111 / 0.903508
Min / 311 / 1283 / 1485 / 2785 / 910
CC5 / 160 / Mean / 3385 / 8658 / 13449 / 17089 / 3736 / 735.924 / 0.000
Sd / 436.2081 / 435.087 / 741.2973 / 0.944155 / 0.5115
Min / 2630 / 7393 / 11797 / 17085 / 3734
B(2) / 7 / Mean / 0 / 1 / 2 / 3 / 0 / 114.950 / 0.000
Sd / 0 / 1.09619 / 1.506584 / 0 / 0
Min / 0 / 0 / 0 / 3 / 0
B(3) / 15 / Mean / 0 / 12 / 23 / 51 / 12 / 297.150 / 0.000
Sd / 0 / 4.827641 / 6.307883 / 0.651842 / 0.424264
Min / 0 / 8 / 8 / 48 / 10
B(4) / 31 / Mean / 0 / 79 / 127 / 295 / 40 / 271.819 / 0.000
Sd / 0 / 13.97876 / 25.59994 / 0.377424 / 0.532993
Min / 0 / 64 / 73 / 293 / 38
B(5) / 63 / Mean / 0 / 391 / 583 / 1351 / 122 / 260.834 / 0.000
Sd / 0 / 33.29669 / 74.15809 / 1.002853 / 1.363669
Min / 0 / 340 / 413 / 1348 / 115
B(6) / 127 / Mean / 0 / 1748 / 2592 / 6264 / 664 / 261.978 / 0.000
Sd / 0 / 200.4453 / 191.8993 / 1.465801 / 0.857381
Min / 0 / 1548 / 2100 / 6259 / 660
X(2) / 7 / Mean / 2 / 6 / 7 / 11 / 10 / 826.151 / 0.000
Sd / 1.281581 / 1.973394 / 2.956901 / 0.997139 / 0.926041
Min / 0 / 2 / 1 / 8 / 7
X(3) / 15 / Mean / 14 / 44 / 76 / 122 / 64 / 734.945 / 0.000
Sd / 4.531072 / 11.88566 / 16.46405 / 0.902604 / 0.899887
Min / 6 / 23 / 37 / 118 / 60
X(4) / 31 / Mean / 62 / 203 / 451 / 728 / 249 / 520.595 / 0.000
Sd / 16.04311 / 53.75448 / 57.48865 / 0.638877 / 0.868731
Min / 34 / 127 / 353 / 725 / 245
X(5) / 63 / Mean / 220 / 827 / 2187 / 3444 / 1082 / 457.499 / 0.000
Sd / 64.83974 / 140.9309 / 168.1643 / 1.05463 / 1.049003
Min / 113 / 575 / 1856 / 3440 / 1078
X(6) / 127 / Mean / 679 / 2665 / 9696 / 15438 / 4112 / 365.070 / 0.000
Sd / 153.9097 / 354.5721 / 560.1531 / 0.569998 / 1.620783
Min / 449 / 2083 / 8463 / 15435 / 4107
P(8) / 12 / Mean / 3 / 17 / 19 / 20 / 20 / 1015.473 / 0.000
Sd / 1.48791 / 6.216535 / 6.095331 / 0.619743 / 0.552914
Min / 0 / 8 / 7 / 17 / 17
P(16) / 16 / Mean / 34 / 88 / 116 / 171 / 93 / 1124.176 / 0.000
Sd / 10.51881 / 27.98925 / 19.45533 / 1.718566 / 0.604743
Min / 19 / 45 / 76 / 160 / 90
P(32) / 32 / Mean / 146 / 445 / 573 / 1063 / 433 / 768.397 / 0.000
Sd / 27.13973 / 53.73103 / 69.49396 / 0.842978 / 0.60068
Min / 100 / 347 / 437 / 1059 / 430
T2 / 6 / Mean / 2 / 4 / 5 / 7 / 8 / 992.034 / 0.000
Sd / 1.503194 / 1.445048 / 1.981959 / 0.469911 / 0.552914
Min / 0 / 1 / 1 / 5 / 5
T3 / 10 / Mean / 10 / 23 / 31 / 54 / 28 / 892.464 / 0.000
Sd / 3.988555 / 6.977544 / 8.141328 / 0.723935 / 0.638877
Min / 3 / 15 / 13 / 51 / 25
T4 / 15 / Mean / 26 / 68 / 110 / 148 / 73 / 974.513 / 0.000
Sd / 6.969321 / 13.16216 / 19.98699 / 0.820403 / 0.571429
Min / 12 / 51 / 61 / 145 / 70
T5 / 21 / Mean / 65 / 155 / 266 / 425 / 154 / 717.467 / 0.000
Sd / 18.39805 / 26.72426 / 34.33803 / 1.059264 / 1.20136
Min / 27 / 114 / 196 / 420 / 150
T6 / 28 / Mean / 127 / 268 / 568 / 795 / 330 / 753.609 / 0.000
Sd / 32.04212 / 44.84366 / 68.27428 / 0.891914 / 1.28174
Min / 66 / 217 / 415 / 790 / 323
T7 / 36 / Mean / 218 / 432 / 1023 / 1585 / 469 / 550.252 / 0.000
Sd / 48.293 / 66.5758 / 125.0632 / 1.087217 / 0.886405
Min / 134 / 364 / 682 / 1580 / 465
T8 / 45 / Mean / 343 / 708 / 1769 / 2580 / 754 / 547.748 / 0.000
Sd / 84.39194 / 119.786 / 154.2224 / 0.914509 / 1.331104
Min / 190 / 566 / 1484 / 2575 / 748
T9 / 55 / Mean / 523 / 1028 / 2825 / 4273 / 1549 / 558.842 / 0.000
Sd / 116.7842 / 168.9926 / 235.9958 / 1.042759 / 1.938756
Min / 345 / 840 / 2264 / 4269 / 1545
T10 / 66 / Mean / 728 / 1480 / 4336 / 6353 / 1720 / 477.902 / 0.000
Sd / 150.8079 / 233.6195 / 261.8215 / 0.998162 / 1.189066
Min / 459 / 1180 / 3697 / 6349 / 1715
C2XC2 / 4 / Mean / 0 / 0 / 0 / 0 / 0 / - / -
Sd / 0 / 0 / 0 / 0 / 0
Min / 0 / 0 / 0 / 0 / 0
C3XC3 / 9 / Mean / 18 / 31 / 31 / 52 / 24 / 1599.914 / 0.000
Sd / 2.404163 / 3.219583 / 7.346358 / 0.619743 / 1.002853
Min / 13 / 24 / 18 / 49 / 20
C4XC4 / 16 / Mean / 60 / 151 / 129 / 273 / 120 / 1053.658 / 0.000
Sd / 8.156355 / 1.921309 / 25.3395 / 0.788954 / 0.895339
Min / 45 / 147 / 87 / 270 / 117
C5XC5 / 25 / Mean / 133 / 330 / 346 / 671 / 306 / 1017.942 / 0.000
Sd / 19.61778 / 20.2086 / 54.80862 / 0.934814 / 1.255843
Min / 100 / 284 / 248 / 667 / 300
C6XC6 / 36 / Mean / 254 / 720 / 775 / 1792 / 595 / 637.270 / 0.000
Sd / 32.20407 / 13.0092 / 72.8813 / 0.670059 / 1.124132
Min / 195 / 692 / 585 / 1790 / 590
C7XC7 / 49 / Mean / 439 / 1147 / 1446 / 2866 / 992 / 709.937 / 0.000
Sd / 68.89744 / 37.15494 / 133.0098 / 1.088155 / 1.169162
Min / 332 / 1079 / 1136 / 2860 / 987
C8XC8 / 64 / Mean / 657 / 1961 / 2577 / 6316 / 1223 / 405.069 / 0.000
Sd / 82.91941 / 31.44711 / 208.7571 / 1.261842 / 1.404948
Min / 491 / 1890 / 2096 / 6310 / 1219
C9XC9 / 81 / Mean / 970 / 2742 / 4139 / 8403 / 2279 / 520.657 / 0.000
Sd / 151.3051 / 72.97905 / 341.7716 / 1.460361 / 1.100835
Min / 710 / 2607 / 3500 / 8400 / 2275
C10XC10 / 100 / Mean / 1388 / 4109 / 6522 / 16364.08 / 2779 / 234679.116 / 0.000
Sd / 181.6133 / 55.11752 / 413.3213 / 0.965528 / 1.049003
Min / 1070 / 3997 / 5527 / 16360 / 2775
S(4) / 4 / Mean / 0 / 0 / 1 / 1 / 1 / 89.315 / 0.000
Sd / 0 / 0 / 0.484873 / 0.239898 / 0.141421
Min / 0 / 0 / 0 / 0 / 0
S(5) / 5 / Mean / 1 / 2 / 2 / 3 / 2 / 567.190 / 0.000
Sd / 0.501427 / 0.505076 / 0.942424 / 0.347586 / 0.24661
Min / 0 / 1 / 0 / 1 / 0
S(6) / 6 / Mean / 3 / 7 / 5 / 9 / 8 / 1846.614 / 0.000
Sd / 0 / 0 / 1.895645 / 0.824126 / 0.449943
Min / 3 / 7 / 3 / 5 / 5
S(7) / 7 / Mean / 8 / 16 / 11 / 19 / 15 / 2531.302 / 0.000
Sd / 0.989743 / 0.478518 / 2.672612 / 0.682433 / 1.087968
Min / 6 / 15 / 6 / 15 / 10
S(8) / 8 / Mean / 16 / 33 / 24 / 36 / 33 / 3224.317 / 0.000
Sd / 0 / 0 / 5.588801 / 1.084962 / 0.755929
Min / 16 / 33 / 16 / 31 / 30
S(9) / 9 / Mean / 29 / 57 / 40 / 61 / 56 / 3567.900 / 0.000
Sd / 1.514016 / 0.484873 / 8.828433 / 0.998162 / 1.292995
Min / 27 / 56 / 30 / 57 / 50
S(10) / 10 / Mean / 50 / 96 / 65 / 101 / 97 / 3765.867 / 0.000
Sd / 0 / 0 / 10.90695 / 1.340271 / 1.284762
Min / 50 / 96 / 52 / 95 / 96
S(15) / 15 / Mean / 334 / 582 / 384 / 588 / 582 / 4816.206 / 0.000
Sd / 3.020745 / 0.484873 / 26.30267 / 1.237014 / 1.382692
Min / 330 / 581 / 338 / 582 / 576
S(20) / 20 / Mean / 1200 / 2016 / 1358 / 2026 / 2016 / 5437.306 / 0.000
Sd / 0 / 0 / 100.0364 / 1.420118 / 1.139996
Min / 1200 / 2016 / 1232 / 2020 / 2010
S(25) / 25 / Mean / 3141 / 5137 / 3433 / 5148 / 5137 / 5717.332 / 0.000
Sd / 5.538032 / 0.503457 / 214.1157 / 1.440521 / 1.087217
Min / 3135 / 5136 / 3164 / 5140 / 5131
S(30) / 30 / Mean / 6825 / 11011 / 7335 / 11026 / 11012 / 5886.062 / 0.000
Sd / 0 / 0 / 367.4035 / 0.888934 / 1.075895
Min / 6825 / 11011 / 6891 / 11023 / 11008
S(35) / 35 / Mean / 13049 / 20792 / 13953 / 20809 / 20792 / 6158.446 / 0.000
Sd / 8.074753 / 0.501427 / 572.208 / 0.880631 / 1.029365
Min / 13040 / 20791 / 13257 / 20806 / 20786
S(40) / 40 / Mean / 22800 / 36081 / 24215 / 36101 / 36082 / 6268.586 / 0.000
Sd / 0 / 0 / 806.003 / 1.092647 / 0.958102
Min / 22800 / 36081 / 23144 / 36097 / 36076
S(45) / 45 / Mean / 37178 / 58422 / 38913 / 58444 / 58422 / 6276.665 / 0.000
Sd / 10.2966 / 0.498569 / 1139.056 / 1.076843 / 1.099907
Min / 37170 / 58421 / 37545 / 58440 / 58418
S(50) / 50 / Mean / 61947 / 92455 / 64924 / 96325 / 96302 / 6643.477 / 0.000
Sd / 144.9013 / 7544.827 / 2093.941 / 0.968061 / 1.142857
Min / 61796 / 62864 / 62627 / 96321 / 96299

Table 2. Results on random graphs for different heuristics for vertex ordering

n=|V| / rdfs / rbfs / rand / Vcover / maxNbr / F-value / p-value
40 / Mean / 6694 / 8520 / 8220 / 10889 / 8695 / 514.513 / 0.00
Sd / 334.4334 / 400.1506 / 435.5663 / 20.54105893 / 15.00097
Min / 6009 / 7804 / 7101 / 10779 / 8599
50 / Mean / 17430 / 21506 / 20819 / 26441 / 20780 / 17407.723 / 0.00
Sd / 699.9343 / 723.1122 / 863.5149 / 731.591 / 686.8343067
Min / 16261 / 20132 / 19228 / 24759 / 19331
60 / Mean / 38298 / 45197 / 43673 / 54837 / 42419 / 45766.676 / 0.00
Sd / 1290.958 / 1202.054 / 1595.302 / 14.89122 / 25.56647
Min / 35345 / 42858 / 39852 / 54800 / 42332

Table 3: Results of standard graphs for edge distribution heuristics