Algorithm #1: Random vertex order greedy

  1. Choose a random permutation p of 0 to n-1.
  2. Run the algorithm from assignment #2 with these changes: At a given level, choose u= p[level] to be the vertex that is first colored blue then colored red.
  3. The algorithm terminates as soon as you find the first small dominating set.
Do repeated random trials until you run out of time.

Student Results

These are best viewed on a wide screen with a small font size.

C80 fullerenes:
 
  #     n :  k 1    k 2    k 3    k 4    k 5    k 6    k 7    k 8    k 9    k10    k11    k12    k13    k14    k15    k16    k17    k18    k19  
  1    80 :   20     22-    27     25     22-    23     80+   ---     24     27     23    ---     22-    26     22-    22-    22-   ---    ---  
  2    80 :   20     22-    27    ---     23     22-    80+   ---     25     26     23    ---     22-    26     22-    22-    25    ---    ---  
  3    80 :   20     22-    24    ---     22-    22-    80+   ---     24     26     24    ---     22-    28     22-    22-    27    ---    ---  
  4    80 :   20     22-    24    ---     22-    22-    80+   ---     25     25     24    ---     22-    27     23     22-    26    ---    ---  
  5    80 :   20     23     24    ---     22-    23     80+   ---     23     27     25    ---     22-    26     22-    22-    26    ---    ---  
  6    80 :   20     22-    28    ---     22-    23     80+   ---     25     27     24    ---     22-    27     22-    22-    27    ---    ---  
  7    80 :   20     22-    27    ---     22-    22-    80+   ---     25     25     25    ---     23     26     22-    22-    28    ---    ---  
  8    80 :   20     22-    26    ---     22-    22-    80+   ---     24     27     25    ---     22-    25     22-    22-    28    ---    ---  
  9    80 :   20     22     27    ---     23     20-    80+   ---     25     27     24    ---     22     28     22     22     25    ---    ---  
 10    80 :   20     22-    28    ---     23     22-    80+   ---     25     26     25    ---     22-    26     22-    22-    27    ---    ---  
 11    80 :   20     22     27    ---     22     22     80+   ---     24     26     26    ---     22     29     22     20-    27    ---    ---  
 12    80 :   21     23     26    ---     23     23     80+   ---     23     27     26    ---     22-    26     23     22-    26    ---    ---  
 13    80 :   21     22     27    ---     23     22     80+   ---     24     27     25    ---     22     25     23     21-    28    ---    ---  
 14    80 :   21     22-    23    ---     23     23     80+   ---     24     25     25    ---     22-    28     22-    23     28    ---    ---  
 15    80 :   21     22-    27    ---     23     23     80+   ---     26     27     25    ---     22-    28     23     22-    28    ---    ---  
 16    80 :   21     22-    26    ---     23     22-    80+   ---     26     27     25    ---     23     25     23     22-    27    ---    ---  
 17    80 :   21     22-    26    ---     23     23     80+   ---     26     24     24    ---     22-    26     23     23     26    ---    ---  
 18    80 :   21     23     26    ---     23     23     80+   ---     26     24     25    ---     22-    26     22-    22-    25    ---    ---  
 19    80 :   21     22-    25    ---     23     22-    80+   ---     25     26     24    ---     22-    26     22-    22-    25    ---    ---  
 20    80 :   21     22-    26    ---     23     22-    80+   ---     24     27     24    ---     23     28     23     22-    25    ---    ---  
 21    80 :   21     23     25    ---     23     23     80+   ---     24     26     24    ---     22-    26     22-    22-    25    ---    ---  
 22    80 :   21     22-    25    ---     23     22-    80+   ---     24     26     24    ---     22-    26     23     23     26    ---    ---  
 23    80 :   22     22-    25    ---     23     23     80+   ---     25     25     24    ---     22-    25     23     23     26    ---    ---  
 24    80 :   22     23     25    ---     24     23     80+   ---     23     26     24    ---     22-    26     23     22-    27    ---    ---  
 25    80 :   22     22-    29    ---     23     23     80+   ---     24     27     25    ---     22-    27     23     22-    26    ---    ---  
 26    80 :   22     23     29    ---     23     23     80+   ---     26     27     24    ---     22-    27     22-    22-    26    ---    ---  
 27    80 :   22     22-    29    ---     22-    22-    80+   ---     26     27     24    ---     22-    27     22-    22-    28    ---    ---  
 28    80 :   22     23     28+   ---     22-    22-   ---    ---     26     27     24    ---     22-    25     23     22-    25    ---    ---  
 29    80 :   22     22-    26    ---     22-    23    ---    ---     25     27+    24    ---     23     27+    22-    22-    26    ---    ---  
 30    80 :   22     22-    26    ---     22-    23    ---    ---     24     28     24    ---     23     24     22-    22-    30+   ---    ---  
 31    80 :   22     22-    26    ---     23     22-   ---    ---     24     26     24    ---     23     28+    22-    22-    25    ---    ---  
 32    80 :   22     23     26    ---     23     22-   ---    ---     27     26     24    ---     22-    29+    23     22-    27    ---    ---  
 33    80 :   22     23     27+   ---     23     22-   ---    ---     26     25     24    ---     23     26     22-    22-    27+   ---    ---  

Rank  1: Student 16 with score  34
Rank  2: Student 13 with score  40
Rank  3: Student  2 with score  42
=====================================
Rank  4: Student  6 with score  46
Rank  4: Student 15 with score  46
Rank  6: Student  5 with score  55
Rank  7: Student 11 with score 111
Rank  8: Student  9 with score 124
Rank  9: Student 10 with score 173
Rank 10: Student  3 with score 174
Rank 11: Student 17 with score 177
Rank 12: Student 14 with score 182
Rank 13: Student  7 with score 2079
Rank 14: Student  4 with score 2565
Rank 15: Student  8 with score 2640
Rank 15: Student 12 with score 2640
Rank 15: Student 18 with score 2640
Rank 15: Student 19 with score 2640

 
Football distance 1:
 
  #     n :  k 1    k 2    k 3    k 4    k 5    k 6    k 7    k 8    k 9    k10    k11    k12    k13    k14    k15    k16    k17    k18    k19  
  1     9 :    3      3-     3-     3-     3-     3-     3-     3-     3-     3-     3-   ---      3-     3-     3-     3-     3-   ---      3- 
  2    27 :    5      5-     7+   ---      5-     5-     5-     5-     5-     5-     5-   ---      5-     5-     5-     5-     7+   ---      5- 
  3    81 :    9      9-    15    ---     27+     9-    16     12      9-    16     12    ---      9-    16      9-     9-    17    ---     14  
  4   243 :   27     36     40    ---     81     36    243+    41     40     38     42    ---     35-    43     36     35-    42    ---     41  
  5   729 :   73    107    114    ---    243    108    729+   112    112    118    112    ---    106    115    109    104-   116    ---    113  
  6  2187 :  186    306    309    ---    729+   305    ---    326    316    309    311    ---    ---    316    302-   303    321    ---    315  

Rank  1: Student 16 with score 156
Rank  2: Student 15 with score 161
Rank  3: Student  2 with score 163
Rank  3: Student  6 with score 163
=====================================
Rank  5: Student  9 with score 182
Rank  5: Student 11 with score 182
Rank  7: Student  3 with score 185
Rank  8: Student 10 with score 186
Rank  9: Student 19 with score 188
Rank 10: Student 14 with score 195
Rank 11: Student  8 with score 196
Rank 12: Student 17 with score 203
Rank 13: Student  5 with score 785
Rank 14: Student 13 with score 2228
Rank 15: Student  7 with score 3066
Rank 16: Student  4 with score 3267
Rank 17: Student 12 with score 3276
Rank 17: Student 18 with score 3276

 
Football distance 2:
 
  #     n :  k 1    k 2    k 3    k 4    k 5    k 6    k 7    k 8    k 9    k10    k11    k12    k13    k14    k15    k16    k17    k18    k19  
  1    27 :    3      3-     3-     3-     3-     3-     3-     3-     3-     3-     3-   ---      3-     3-     3-     3-     3-   ---      3- 
  2    81 :    3      3-     6+   ---      4      3-     3-     3-     3-     3-     3-   ---      3-     6+     3-     3-     6+   ---      3- 
  3   243 :    8      9-    12    ---     27+     9-    11     10      9-    12     10    ---      9-    13     10      9-    11    ---      9- 
  4   729 :   17     25     30    ---     81     24-   729+    28     26     27     28    ---     24-    28     25     24-    29    ---     26  
  5  2187 :   34     67     69    ---    243     67   2187+    67     66-    70     68    ---    ---     73     67     66-    69    ---     66- 

Rank  1: Student 16 with score  40
Rank  2: Student  6 with score  41
Rank  3: Student  2 with score  42
Rank  3: Student  9 with score  42
Rank  3: Student 19 with score  42
=====================================
Rank  6: Student 15 with score  43
Rank  7: Student  8 with score  46
Rank  8: Student 11 with score  47
Rank  9: Student 10 with score  50
Rank 10: Student 17 with score  53
Rank 11: Student  3 with score  55
Rank 12: Student 14 with score  58
Rank 13: Student  5 with score 293
Rank 14: Student 13 with score 2195
Rank 15: Student  7 with score 2868
Rank 16: Student  4 with score 3240
Rank 17: Student 12 with score 3267
Rank 17: Student 18 with score 3267

 
Football distance 3:
 
  #     n :  k 1    k 2    k 3    k 4    k 5    k 6    k 7    k 8    k 9    k10    k11    k12    k13    k14    k15    k16    k17    k18    k19  
  1    81 :    3      3-     3-     3-     3-     3-     3-     3-     3-     3-     3-   ---      3-     3-     3-     3-     3-   ---      3- 
  2   243 :    3      3-     5    ---      6+     3-     3-     3-     3-     3-     3-   ---      3-     3-     3-     3-     6+   ---      3- 
  3   729 :    6      7     10    ---     27+     8      9      6-    10     11      7    ---      7     10      7      6-    11    ---      7  
  4  2187 :   12     20     21    ---     81+    19     27     19     19     19     19    ---    ---     21     19     18-    22    ---     19  

Rank  1: Student 16 with score   6
Rank  2: Student  8 with score   7
Rank  3: Student 11 with score   8
Rank  3: Student 15 with score   8
Rank  3: Student 19 with score   8
Rank  6: Student  2 with score   9
Rank  6: Student  6 with score   9
=====================================
Rank  8: Student  9 with score  11
Rank  9: Student 10 with score  12
Rank 10: Student 14 with score  13
Rank 11: Student  3 with score  15
Rank 12: Student  7 with score  18
Rank 12: Student 17 with score  18
Rank 14: Student  5 with score  93
Rank 15: Student 13 with score 2188
Rank 16: Student  4 with score 3159
Rank 17: Student 12 with score 3240
Rank 17: Student 18 with score 3240

 
Hypercube distance 1:
 
  #     n :  k 1    k 2    k 3    k 4    k 5    k 6    k 7    k 8    k 9    k10    k11    k12    k13    k14    k15    k16    k17    k18    k19  
  1     8 :    2      2-     2-     2-     2-     2-     2-     2-     2-     2-     2-   ---      2-     4+     2-     2-     2-   ---    ---  
  2    16 :    4      4-     4-   ---      4-     4-     4-     4-     4-     4-     4-   ---      4-     4-     4-     4-     5+   ---    ---  
  3    32 :    7      7-     7-   ---      8      7-     7-     7-     7-     7-     7-   ---      7-     8      7-     7-     9+   ---    ---  
  4    64 :   12     12-    16    ---     16     12-    64+    12-    13     14     13    ---     12-    15     12-    12-    14    ---    ---  
  5   128 :   16     20     27    ---     40     21    128+    25     25     26     24    ---     16-    28     22     20     30    ---    ---  
  6   256 :   32     42-    50    ---    128     45    256+    52     51     48     49    ---     43     48     45     45     51    ---    ---  
  7   512 :   62     87     94    ---    256+    90    ---     98     94     95     94    ---     86-    97     87     88     97    ---    ---  
  8  1024 :  120    170-   183    ---    512+   173    ---    179    176    171    180    ---    ---    176    172    171    188    ---    ---  
  9  2048 :  192    334    329    ---   1024+   336    ---    339    334    336    339    ---    ---    328    327    326-   343    ---    ---  

Rank  1: Student 16 with score 228
Rank  2: Student  2 with score 231
Rank  2: Student 15 with score 231
=====================================
Rank  4: Student  6 with score 243
Rank  5: Student 10 with score 256
Rank  6: Student  9 with score 259
Rank  7: Student 14 with score 261
Rank  8: Student  3 with score 265
Rank  8: Student 11 with score 265
Rank 10: Student  8 with score 271
Rank 11: Student 17 with score 292
Rank 12: Student  5 with score 1543
Rank 13: Student 13 with score 3107
Rank 14: Student  7 with score 3972
Rank 15: Student  4 with score 4080
Rank 16: Student 12 with score 4088
Rank 16: Student 18 with score 4088
Rank 16: Student 19 with score 4088

 
Hypercube distance 2:
 
  #     n :  k 1    k 2    k 3    k 4    k 5    k 6    k 7    k 8    k 9    k10    k11    k12    k13    k14    k15    k16    k17    k18    k19  
  1    32 :    2      2-     4+     2-     2-     2-     2-     2-     2-     2-     2-   ---      2-     2-     2-     2-     2-   ---      2- 
  2    64 :    4      4-     5+   ---      4-     4-     4-     4-     4-     4-     4-   ---      4-     5+     4-     4-     5+   ---      4- 
  3   128 :    7      7-     8    ---     16+     7-     8      7-     7-     8      7-   ---      7-     8      7-     7-     9    ---      7- 
  4   256 :   12     13     15    ---     39+    13     16     12-    13     16     14    ---     13     17     13     13     16    ---     15  
  5   512 :   16     24-    27    ---    105     24-   512+    29     31     26     25    ---     24-    31     25     24-    28    ---     26  
  6  1024 :   30     45-    50    ---    237     46   1024+    47     50     46     49    ---    ---     45-    46     45-    49    ---     47  
  7  2048 :   44     83     87    ---    512     84   2048+    89     89     86     89    ---    ---     87     83     82-    85    ---     86  

Rank  1: Student 16 with score  62
Rank  2: Student  2 with score  63
=====================================
Rank  3: Student  6 with score  65
Rank  3: Student 15 with score  65
Rank  5: Student 19 with score  72
Rank  6: Student 10 with score  73
Rank  7: Student  8 with score  75
Rank  7: Student 11 with score  75
Rank  9: Student 17 with score  79
Rank 10: Student 14 with score  80
Rank 11: Student  3 with score  81
Rank 11: Student  9 with score  81
Rank 13: Student  5 with score 800
Rank 14: Student 13 with score 3081
Rank 15: Student  7 with score 3499
Rank 16: Student  4 with score 4032
Rank 17: Student 12 with score 4064
Rank 17: Student 18 with score 4064

 
Hypercube distance 3:
 
  #     n :  k 1    k 2    k 3    k 4    k 5    k 6    k 7    k 8    k 9    k10    k11    k12    k13    k14    k15    k16    k17    k18    k19  
  1   128 :    2      2-     5+     2-     2-     2-     2-     2-     2-     4      2-   ---      2-     4      2-     2-     2-   ---      2- 
  2   256 :    4      4-     4-   ---     16+     4-     4-     4-     4-     7      4-   ---      4-     6      4-     4-     6    ---      4- 
  3   512 :    7      8-    11    ---     40+     8-    10      8-     8-     9      8-   ---      8-    11      8-     8-     8-   ---      8- 
  4  1024 :   12     15     17    ---    108+    16     19     16     15     17     17    ---    ---     18     15     14-    16    ---     16  
  5  2048 :   16     28     26-   ---    237     29   2048+    30     28     30     27    ---    ---     31     28     26-    30    ---     29  

Rank  1: Student 16 with score  13
Rank  2: Student  2 with score  16
Rank  2: Student  9 with score  16
Rank  2: Student 15 with score  16
=====================================
Rank  5: Student 11 with score  17
Rank  6: Student  6 with score  18
Rank  6: Student 19 with score  18
Rank  8: Student  8 with score  19
Rank  9: Student 17 with score  21
Rank 10: Student  3 with score  22
Rank 11: Student 10 with score  26
Rank 12: Student 14 with score  29
Rank 13: Student  5 with score 362
Rank 14: Student  7 with score 2042
Rank 15: Student 13 with score 3073
Rank 16: Student  4 with score 3840
Rank 17: Student 12 with score 3968
Rank 17: Student 18 with score 3968

 
Kneser Graphs:
 
  #     n :  k 1    k 2    k 3    k 4    k 5    k 6    k 7    k 8    k 9    k10    k11    k12    k13    k14    k15    k16    k17    k18    k19  
  1    35 :    7      7-    11+     7-    10      7-     8      7-     7-    10      7-   ---      7-    10      7-     7-     7-   ---      7- 
  2    56 :    7      7-     9    ---     12+     7-     8      7-     7-     9      7-   ---      7-    10      7-     7-    10    ---      7- 
  3    84 :    7      7-     8    ---     19+     7-     7-     7-     7-     8      7-   ---      7-     8      7-     7-     9    ---      7- 
  4   120 :    6      6-     7    ---     22+     6-     6-     6-     6-     8      6-   ---      6-     7      6-     6-     7    ---      6- 
  5   165 :    5      5-     6    ---     25+     5-     5-     5-     5-     7      5-   ---      5-     7      5-     5-     8    ---      5- 
  6   220 :    4      4-     8    ---     28+     4-     4-     4-     4-     6      4-   ---      4-     6      4-     4-     6    ---      4- 
  7   286 :    4      4-     5    ---     31+     4-     4-     4-     4-     4-     4-   ---      4-     7      4-     4-     6    ---      4- 
  8   126 :   26     29     34    ---     56     28-   126+    35     34     33     31    ---     29     37     28-    29     38    ---     30  
  9   210 :   15     23     30    ---     70     24    210+    26     27     28     26    ---     21-    27     24     24     29    ---     25  
 10   330 :   15     19-    23    ---    101+    20     26     22     19-    23     22    ---     19-    22     20     19-    22    ---     22  
 11   495 :   12     17     21    ---    131+    17     21     17     17     18     18    ---     16-    21     16-    16-    22    ---     17  
 12   715 :   10     15     19    ---    165+    15     19     17     15     19     15    ---     14-    15     15     15     18    ---     15  
 13   462 :   66    104    115    ---    210    104    462+   112    109    110    113    ---    102-   112    104    104    116    ---    112  
 14   792 :   56     80     87    ---    330     79-   792+    82     82     83     87    ---     80     87     79-    79-    86    ---     82  
 15  1287 :   39     59-    62    ---    461+    61    ---     64     64     64     62    ---    ---     64     60     59-    67    ---     63  

Rank  1: Student 16 with score 106
Rank  2: Student  2 with score 107
Rank  2: Student 15 with score 107
=====================================
Rank  4: Student  6 with score 109
Rank  5: Student 19 with score 127
Rank  6: Student  9 with score 128
Rank  7: Student 11 with score 135
Rank  8: Student  8 with score 136
Rank  9: Student 10 with score 151
Rank 10: Student 14 with score 161
Rank 11: Student  3 with score 166
Rank 12: Student 17 with score 172
Rank 13: Student 13 with score 1368
Rank 14: Student  5 with score 1392
Rank 15: Student  7 with score 2745
Rank 16: Student  4 with score 5348
Rank 17: Student 12 with score 5383
Rank 17: Student 18 with score 5383

 
Queen Graphs:
 
  #     n :  k 1    k 2    k 3    k 4    k 5    k 6    k 7    k 8    k 9    k10    k11    k12    k13    k14    k15    k16    k17    k18    k19  
  1    16 :    2      2-     2-     2-     2-     2-     2-     2-     2-     2-     2-   ---      2-     3+     2-     2-     2-   ---      2- 
  2    25 :    3      3-     3-   ---      3-     3-     3-     3-     3-     3-     3-   ---      3-     3-     3-     3-     3-   ---      3- 
  3    36 :    3      3-     4    ---      4      3-     3-     3-     3-     5+     3-   ---      3-     5+     3-     3-     4    ---      3- 
  4    49 :    4      4-     5    ---      4-     4-     4-     4-     4-     5      4-   ---      4-     5      4-     4-     6+   ---      4- 
  5    64 :    5      5-     7+   ---      5-     5-     5-     5-     5-     5-     5-   ---      5-     5-     5-     5-     7+   ---      5- 
  6    81 :    5      5-     8+   ---      8+     5-     6      5-     5-     7      5-   ---      5-     7      5-     5-     8+   ---      5- 
  7   100 :    5      6      8    ---      9+     6      6      6      6      9+     5-   ---      5-     9+     5-     5-     8    ---      5- 
  8   121 :    5      6-    10+   ---      9      7      8      7      7      9      7    ---      7     10+     7      6-    10+   ---      8  
  9   144 :    6      8     10    ---     11+     8      9      8      8     10      7-   ---      8     10      8      8     10    ---      8  
 10   169 :    7      8-    12    ---     12      8-    10      9      9     11      9    ---      8-    13+     9      8-    13+   ---      9  
 11   196 :    8      9-    13    ---     13     10     13     10     10     13     11    ---      9-    14+    10      9-    12    ---     10  
 12   225 :    9     11     13    ---     14+    11     13     11     11     12     11    ---     10-    12     11     11     13    ---     11  
 13   256 :    9     11-    13    ---     15+    12     14     12     12     14     12    ---     11-    14     12     12     15+   ---     12  
 14   289 :    9     12-    14    ---     16+    13     14     14     13     15     13    ---     12-    14     12-    12-    15    ---     13  
 15   324 :    9     13-    16    ---     17     14     17     14     15     16     15    ---     13-    18+    14     13-    17    ---     15  
 16   361 :   10     14-    16    ---     18     15     17     16     16     17     16    ---     15     19     15     14-    20+   ---     16  
 17   400 :   11     16     17    ---     19     16    400+    17     17     18     17    ---     15-    19     16     15-    20    ---     17  
 18   441 :   11     17     20    ---     20     17     20     17     17     20     18    ---     17     18     17     16-    21+   ---     17  
 19   484 :   12     18     21    ---     21     18     25+    19     19     21     19    ---     17-    20     18     17-    19    ---     18  
 20   529 :   12     19     22    ---     22     19     23+    20     18-    22     21    ---     18-    23+    19     19     21    ---     20  
 21   576 :   13     20     23    ---     23     20     26+    21     21     23     22    ---     19-    24     20     20     21    ---     21  
 22   625 :   13     21     25    ---     24     21     27+    22     24     25     23    ---     20-    24     21     20-    25    ---     22  
 23   676 :   14     22     26    ---     25     22    676+    22     26     25     23    ---     21-    27     22     21-    26    ---     24  
 24   729 :   14     23-    26    ---     26     24     29+    25     24     24     24    ---     23-    26     24     23-    26    ---     24  
 25   784 :   15     24     28    ---     27     24    ---     24     25     27     28    ---     24     29+    23-    24     27    ---     25  
 26   841 :   15     24-    28    ---     28     26    ---     26     27     29     26    ---     25     27     25     25     31+   ---     28  
 27   900 :   15     26-    30    ---     29     26-   ---     28     28     27     26-   ---     26-    29     27     26-    31+   ---     29  

Rank  1: Student 13 with score 101
Rank  2: Student 16 with score 102
Rank  3: Student  2 with score 106
=====================================
Rank  4: Student 15 with score 113
Rank  5: Student  6 with score 115
Rank  6: Student  8 with score 126
Rank  7: Student 19 with score 130
Rank  8: Student  9 with score 131
Rank  8: Student 11 with score 131
Rank 10: Student 10 with score 170
Rank 11: Student  3 with score 176
Rank 12: Student  5 with score 180
Rank 13: Student 14 with score 183
Rank 14: Student 17 with score 187
Rank 15: Student  7 with score 3696
Rank 16: Student  4 with score 9425
Rank 17: Student 12 with score 9441
Rank 17: Student 18 with score 9441


CSC 425/520 Projects / maintained by Wendy Myrvold / wendym@cs.UVic.ca / revised Nov. 22, 2016