Algorithm #2: Random BFS-order greedy

  1. Randomly select a vertex r to be the root for BFS.
  2. Perform a BFS starting at r. When you visit the neighbours of a vertex, choose a random permutation of the neighbours to be the order in which the neighbours are visited.
  3. Use the algorithm from assignment #2 but at a given level, chose u= queue[level] to be the vertex that you try blue then red (queue is from the BFS).
  4. 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     20-    28     20-    22     20-    80+    20-    23     24    ---    ---     20-    24     20-    20-    20-   ---    ---  
  2    80 :   20     20-    26    ---     23     20-    80+    20-    22     26    ---    ---     20-    26     20-    20-    25    ---    ---  
  3    80 :   20     20-    25    ---     22     20-    80+    20-    23     29    ---    ---     20-    24     20-    20-    24    ---    ---  
  4    80 :   20     20-    27    ---     22     20-    80+    20-    22     28    ---    ---     20-    22     20-    20-    24    ---    ---  
  5    80 :   20     20-    25    ---     22     20-    80+    20-    22     80+   ---    ---     20-    25     20-    20-    25    ---    ---  
  6    80 :   20     20-    26    ---     22     20-    80+    20-    22     27    ---    ---     20-    23     20-    20-    24    ---    ---  
  7    80 :   20     20-    25    ---     22     20-    80+    20-    22     26    ---    ---     20-    23     20-    20-    25    ---    ---  
  8    80 :   20     20-    27    ---     22     20-    80+    20-    22     31    ---    ---     20-    23     20-    20-    23    ---    ---  
  9    80 :   20     20-    28    ---     23     20-    80+    20-    22     80+   ---    ---     20-    23     20-    20-    24    ---    ---  
 10    80 :   20     20-    26    ---     23     20-    80+    20-    22     80+   ---    ---     20-    23     20-    20-    25    ---    ---  
 11    80 :   20     20-    29    ---     22     20-    80+    20-    22     27    ---    ---     20-    22     20-    20-    20-   ---    ---  
 12    80 :   21     21-    27    ---     23     21-    80+    21-    23     80+   ---    ---     21-    23     21-    21-    25    ---    ---  
 13    80 :   21     21-    27    ---     23     21-    80+    21-    22     27    ---    ---     21-   ---     21-    21-    22    ---    ---  
 14    80 :   21     21-    29    ---     23     21-    80+    21-    22     27    ---    ---     21-   ---     21-    21-    23    ---    ---  
 15    80 :   21     21-    26    ---     23     21-    80+    21-    21-    27    ---    ---     21-   ---     21-    21-    23    ---    ---  
 16    80 :   21     21-    26    ---     23     21-    80+    21-    22     80+   ---    ---     21-   ---     21-    21-    22    ---    ---  
 17    80 :   21     21-    28    ---     23     21-    80+    21-    22     27    ---    ---     21-   ---     21-    21-    23    ---    ---  
 18    80 :   21     21-    27    ---     23     21-    80+    21-    23     80+   ---    ---     21-   ---     21-    21-    23    ---    ---  
 19    80 :   21     21-    26    ---     23     21-    80+    21-    21-    80+   ---    ---     21-   ---     21-    21-    23    ---    ---  
 20    80 :   21     21-    26    ---     23     21-    80+    22     22     80+   ---    ---     21-   ---     21-    21-    24    ---    ---  
 21    80 :   21     21-    26    ---     23     21-    80+    21-    22     80+   ---    ---     21-   ---     21-    22     26    ---    ---  
 22    80 :   21     21-    28    ---     23     21-    80+    21-    22     25    ---    ---     21-   ---     21-    21-    24    ---    ---  
 23    80 :   22     22-    26    ---     23     22-    80+    22-    23     28    ---    ---     22-   ---     22-    22-    22-   ---    ---  
 24    80 :   22     22-    27    ---     22-    22-    80+    22-    22-    29    ---    ---     22-   ---     22-    22-    24    ---    ---  
 25    80 :   22     22-    26    ---     23     22-    80+    22-    22-    28    ---    ---     22-   ---     22-    22-    24    ---    ---  
 26    80 :   22     22-    27    ---     23     22-    80+    22-    22-    29    ---    ---     22-   ---     22-    22-    23    ---    ---  
 27    80 :   22     22-    26    ---     22-    22-    80+    22-    22-    28    ---    ---     22-   ---     22-    22-    22-   ---    ---  
 28    80 :   22     22-    27    ---     22-    22-   ---     22-    22-    80+   ---    ---     22-   ---     22-    22-    22-   ---    ---  
 29    80 :   22     22-    26    ---     22-    22-   ---     22-    22-    80+   ---    ---     22-   ---     22-    22-    23    ---    ---  
 30    80 :   22     22-    26+   ---     22-    22-   ---     22-    22-    26+   ---    ---     22-   ---     22-    22-    24    ---    ---  
 31    80 :   22     22-    25+   ---     23     22-   ---     22-    22-    25+   ---    ---     22-   ---     22-    22-    24    ---    ---  
 32    80 :   22     22-    25    ---     23     22-   ---     22-    22-    26+   ---    ---     22-   ---     22-    22-    24    ---    ---  
 33    80 :   22     22-    25    ---     23     22-   ---     22-    22-    80+   ---    ---     22-   ---     22-    22-    23    ---    ---  

Rank  1: Student  2 with score   0
Rank  1: Student  6 with score   0
Rank  1: Student 13 with score   0
Rank  1: Student 15 with score   0
=====================================
Rank  5: Student  8 with score   1
Rank  5: Student 16 with score   1
Rank  7: Student  9 with score  36
Rank  8: Student  5 with score  53
Rank  9: Student 17 with score  79
Rank 10: Student  3 with score 181
Rank 11: Student 10 with score 837
Rank 12: Student 14 with score 1720
Rank 13: Student  7 with score 2079
Rank 14: Student  4 with score 2560
Rank 15: Student 11 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-    10+   ---  
  2    27 :    5      5-     6    ---      5-     5-     5-     5-     5-     6    ---    ---      5-     7      5-     5-     6     28+   ---  
  3    81 :    9      9-    17    ---     27      9-    81+     9-    12     81+   ---    ---      9-    13      9-     9-    17    ---    ---  
  4   243 :   27     36     38    ---     81     37    243+    44     43    243+   ---    ---     35-    50     37     37     40    ---    ---  
  5   729 :   73    104    118    ---    243    106    729+   112    138    729+   ---    ---    103    114    103    101-   113    ---    ---  
  6  2187 :  186    290-   313    ---    729+   293    ---    298    360    ---    ---    ---    ---    301    299    308    308    ---    ---  

Rank  1: Student  2 with score 144
=====================================
Rank  2: Student  6 with score 150
Rank  3: Student 15 with score 153
Rank  4: Student 16 with score 160
Rank  5: Student  8 with score 168
Rank  6: Student 17 with score 184
Rank  7: Student 14 with score 185
Rank  8: Student  3 with score 192
Rank  9: Student  9 with score 258
Rank 10: Student  5 with score 785
Rank 11: Student 13 with score 2225
Rank 12: Student  7 with score 3131
Rank 13: Student 10 with score 3132
Rank 14: Student  4 with score 3267
Rank 15: Student 18 with score 3270
Rank 16: Student 11 with score 3276
Rank 16: Student 12 with score 3276
Rank 16: Student 19 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- 
  2    81 :    3      3-     3-   ---      4      3-     5      3-     3-     6+   ---    ---      3-     6+     3-     3-     5    ---      3- 
  3   243 :    8      9-    11    ---     27+    10     11     10     11     13    ---    ---      9-    14      9-     9-    10    ---     12  
  4   729 :   17     25-    31    ---     81     26    729+    28     28     70    ---    ---     26     27     26     26     27    ---     29  
  5  2187 :   34     70     74    ---    243     69   2187+    75     79     77    ---    ---    ---     71     67-    71     71    ---     74  

Rank  1: Student 15 with score  43
Rank  2: Student  2 with score  45
=====================================
Rank  3: Student  6 with score  46
Rank  4: Student 16 with score  47
Rank  5: Student 17 with score  51
Rank  6: Student  8 with score  54
Rank  7: Student 14 with score  56
Rank  7: Student 19 with score  56
Rank  9: Student  3 with score  57
Rank 10: Student  9 with score  59
Rank 11: Student 10 with score 104
Rank 12: Student  5 with score 293
Rank 13: Student 13 with score 2197
Rank 14: Student  7 with score 2870
Rank 15: Student  4 with score 3240
Rank 16: Student 11 with score 3267
Rank 16: Student 12 with score 3267
Rank 16: 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- 
  2   243 :    3      3-     5    ---      6+     3-     3-   ---      3-     4    ---    ---      3-     6+     3-     3-     5    ---      3- 
  3   729 :    6      8     10    ---     27      8    729+   ---     10     10    ---    ---      6-    10      8     10     11    ---      9  
  4  2187 :   12     21-    21-   ---     81     21-  2187+   ---     23     23    ---    ---    ---     26     24     24     24    ---     24  

Rank  1: Student  2 with score  11
Rank  1: Student  6 with score  11
=====================================
Rank  3: Student 15 with score  14
Rank  4: Student  3 with score  15
Rank  4: Student  9 with score  15
Rank  4: Student 19 with score  15
Rank  7: Student 10 with score  16
Rank  7: Student 16 with score  16
Rank  9: Student 17 with score  19
Rank 10: Student 14 with score  21
Rank 11: Student  5 with score  93
Rank 12: Student 13 with score 2187
Rank 13: Student  7 with score 2898
Rank 14: Student  4 with score 3159
Rank 15: Student  8 with score 3240
Rank 15: Student 11 with score 3240
Rank 15: Student 12 with score 3240
Rank 15: 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-     2-     2-     2-     2-   ---  
  2    16 :    4      4-     4-   ---      4-     4-     4-     4-     4-     5    ---    ---      4-     5      4-     4-     4-    17+   ---  
  3    32 :    7      7-     8    ---      8      7-     7-     7-     7-     9    ---    ---      7-     9      7-     7-    12     33+   ---  
  4    64 :   12     12-    15    ---     16     12-    64+    12-    12-    64+   ---    ---     12-    15     12-    12-    14    ---    ---  
  5   128 :   16     22     28    ---     51     16-   128+    23     23     28    ---    ---     21     26     21     20     30    ---    ---  
  6   256 :   32     44     56    ---    128     41-   256+    48     63    256+   ---    ---     41-    52     41-    44     53    ---    ---  
  7   512 :   62     85-    97    ---    256     87    512+    89    116     99    ---    ---     85-    89     87     89     98    ---    ---  
  8  1024 :  120    164    177    ---    512+   164    ---    172    326    ---    ---    ---    ---    174    163-   175    171    ---    ---  
  9  2048 :  192    316-   343    ---   1024+   319    ---    323    394    ---    ---    ---    ---    333    318    337    329    ---    ---  

Rank  1: Student  6 with score 205
Rank  2: Student 15 with score 208
Rank  3: Student  2 with score 209
=====================================
Rank  4: Student  8 with score 233
Rank  5: Student 16 with score 243
Rank  6: Student 14 with score 258
Rank  7: Student 17 with score 266
Rank  8: Student  3 with score 283
Rank  9: Student  9 with score 500
Rank 10: Student  5 with score 1554
Rank 11: Student 13 with score 3109
Rank 12: Student 10 with score 3400
Rank 13: Student  7 with score 3910
Rank 14: Student 18 with score 4071
Rank 15: Student  4 with score 4080
Rank 16: Student 11 with score 4088
Rank 16: Student 12 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-     4+     2-     2-     2-   ---      2- 
  2    64 :    4      4-     5    ---      4-     4-     4-     4-     4-     6+   ---    ---      4-     6+     4-     4-     5    ---      4- 
  3   128 :    7      7-     9    ---     16+     7-    10      7-     7-    10    ---    ---      7-     8      7-     7-     9    ---      7- 
  4   256 :   12     13     15    ---     40     13    256+    13     13     30    ---    ---     13     17     12-    13     16    ---     15  
  5   512 :   16     24-    28    ---    108     24-   512+    25     28     28    ---    ---     24-    27     25     24-    28    ---     26  
  6  1024 :   30     43-    51    ---    242     44   1024+    50     52     50    ---    ---    ---     48     45     47     48    ---     49  
  7  2048 :   44     80-    92    ---    503     83   2048+    86     86     92    ---    ---    ---     89     81     85     82    ---     90  

Rank  1: Student  2 with score  58
=====================================
Rank  2: Student 15 with score  61
Rank  3: Student  6 with score  62
Rank  4: Student 16 with score  67
Rank  5: Student  8 with score  72
Rank  6: Student 17 with score  75
Rank  7: Student  9 with score  77
Rank  8: Student 19 with score  78
Rank  9: Student 14 with score  84
Rank 10: Student  3 with score  89
Rank 11: Student 10 with score 103
Rank 12: Student  5 with score 800
Rank 13: Student 13 with score 3081
Rank 14: Student  7 with score 3741
Rank 15: Student  4 with score 4032
Rank 16: Student 11 with score 4064
Rank 16: Student 12 with score 4064
Rank 16: 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-     2-     2-     2-     2-     2-     2-     2-     2-   ---    ---      2-     2-     2-     2-     2-   ---      2- 
  2   256 :    4      4-     5    ---     16+     4-     6      4-     4-     7    ---    ---      4-     6      4-     4-     5    ---      4- 
  3   512 :    7      8     10    ---     40      9    512+     7-     9     12    ---    ---      7-    13      8      9     14    ---     10  
  4  1024 :   12     16     17    ---    108     15   1024+    19     16     52    ---    ---    ---     18     14-    16     21    ---     16  
  5  2048 :   16     28     32    ---    237     28   2048+    29     34     33    ---    ---    ---     31     27-    31     30    ---     31  

Rank  1: Student 15 with score  14
Rank  2: Student  2 with score  17
Rank  2: Student  6 with score  17
=====================================
Rank  4: Student  8 with score  20
Rank  5: Student 16 with score  21
Rank  6: Student 19 with score  22
Rank  7: Student  9 with score  24
Rank  8: Student  3 with score  25
Rank  9: Student 14 with score  29
Rank 10: Student 17 with score  31
Rank 11: Student 10 with score  65
Rank 12: Student  5 with score 362
Rank 13: Student 13 with score 3072
Rank 14: Student  7 with score 3551
Rank 15: Student  4 with score 3840
Rank 16: Student 11 with score 3968
Rank 16: Student 12 with score 3968
Rank 16: 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-    10      7-     9      7-     8      7-     7-    10    ---    ---      7-    10      7-    10      7-    36+     7- 
  2    56 :    7      7-     9    ---     12+     7-     8      7-     7-    10    ---    ---      7-    10      7-     7-     9    ---      7- 
  3    84 :    7      7-     8    ---     16+     7-     8      7-     7-     8    ---    ---      7-     8      7-     7-     8    ---      7- 
  4   120 :    6      6-     6-   ---     22+     6-     6-     6-     6-     9    ---    ---      6-     7      6-     6-     8    ---      6- 
  5   165 :    5      5-     8    ---     25+     5-     5-     5-     5-     8    ---    ---      5-     7      5-     5-     9    ---      5- 
  6   220 :    4      4-     7    ---     28+     4-     4-     4-     4-     6    ---    ---      4-     7      4-     4-     7    ---      4- 
  7   286 :    4      4-     5    ---     31+     4-     4-     4-     4-     6    ---    ---      4-     7      4-     4-     7    ---      4- 
  8   126 :   26     28-    35    ---     56     28-   126+    32     35     33    ---    ---     28-    32     29     29     35    ---     31  
  9   210 :   15     23-    28    ---     70     24    210+    28     30    210+   ---    ---     24     28     25     24     32    ---     27  
 10   330 :   15     19     22    ---    101     20    330+    20     24    330+   ---    ---     19     24     18-    19     26    ---     21  
 11   495 :   12     17     19    ---    131     17    495+    17     19     20    ---    ---     16-    20     18     18     22    ---     19  
 12   715 :   10     15     17    ---    165+    16     19     15     16     19    ---    ---     14-    17     15     15     18    ---     18  
 13   462 :   66    102    113    ---    210    104    462+   107    113    462+   ---    ---    101-   104    103    105    110    ---    111  
 14   792 :   56     86     82-   ---    330     89    ---    105    140    792+   ---    ---     84    105     88     86     99    ---     84  
 15  1287 :   39     66     62-   ---    461+    68    ---     84     87     65    ---    ---    ---     87     67     71     84    ---     65  

Rank  1: Student  2 with score 117
=====================================
Rank  2: Student 15 with score 124
Rank  3: Student  6 with score 127
Rank  4: Student 16 with score 131
Rank  5: Student 19 with score 137
Rank  6: Student  3 with score 152
Rank  7: Student  8 with score 169
Rank  8: Student 14 with score 194
Rank  9: Student 17 with score 202
Rank 10: Student  9 with score 225
Rank 11: Student 13 with score 1373
Rank 12: Student  5 with score 1388
Rank 13: Student 10 with score 1709
Rank 14: Student  7 with score 3580
Rank 15: Student  4 with score 5348
Rank 16: Student 18 with score 5377
Rank 17: Student 11 with score 5383
Rank 17: Student 12 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-     3+     2-     2-     2-     2-     2- 
  2    25 :    3      3-     3-   ---      3-     3-     3-     3-     3-     5    ---    ---      3-     3-     3-     3-     5     26+     3- 
  3    36 :    3      3-     4    ---      4      3-     4      3-     3-     4    ---    ---      3-     5+     3-     3-     5+   ---      3- 
  4    49 :    4      4-     4-   ---      4-     4-     5      4-     4-     6+   ---    ---      4-     6+     4-     4-     5    ---      4- 
  5    64 :    5      5-     6    ---      6      5-     6      5-     5-     5-   ---    ---      5-     8+     5-     5-     6    ---      5- 
  6    81 :    5      5-     7    ---      8+     5-     6      5-     5-     6    ---    ---      5-     8+     5-     5-     6    ---      6  
  7   100 :    5      6-     9+   ---      9+     6-     8      6-     6-     8    ---    ---      6-     8      6-     6-     9+   ---      6- 
  8   121 :    5      7      9    ---     10      7     11+     7      8     11+   ---    ---      6-    11+     7      6-    11+   ---      7  
  9   144 :    6      8     10    ---     11      7-    10      9      9     12+   ---    ---      8     11      8      7-    12+   ---      7- 
 10   169 :    7      9     11    ---     12+     9     11      9      9     12+   ---    ---      9     10      9      8-    11    ---      9  
 11   196 :    8     10     12    ---     13+    10     13+    10     10     13+   ---    ---      9-    13+     9-     9-    13+   ---     11  
 12   225 :    9     10-    13    ---     14     12     14     12     12     15+   ---    ---     11     15+    11     11     15+   ---     12  
 13   256 :    9     12-    14    ---     15     12-   256+    13     14     13    ---    ---     12-    16     12-    12-    14    ---     13  
 14   289 :    9     12-    16    ---     16     13    289+    16     14     16    ---    ---     12-    15     13     13     15    ---     14  
 15   324 :    9     14     15    ---     17     14    324+    15     15     18    ---    ---     13-    17     14     14     17    ---     15  
 16   361 :   10     14-    17    ---     18     16     21+    15     16     18    ---    ---     15     17     15     15     19    ---     16  
 17   400 :   11     16     20    ---     19     16    400+    19     18     20    ---    ---     14-    20     16     16     18    ---     17  
 18   441 :   11     16-    21    ---     20     17     22     20     25     33+   ---    ---     16-    20     17     17     21    ---     20  
 19   484 :   12     18-    20    ---     21     19     23     21     21     24    ---    ---     18-    24     18-    19     27+   ---     20  
 20   529 :   12     20     22    ---     22     20    529+    20     25     25    ---    ---     18-    21     20     18-    24    ---     23  
 21   576 :   13     21     21    ---     23     20-   576+    25     22     25    ---    ---     21     26     20-    22     26    ---     23  
 22   625 :   13     21-    25    ---     24     22    625+    26     25     23    ---    ---     21-    29     22     23     25    ---     27  
 23   676 :   14     24     28    ---     25     25    ---     27     26     25    ---    ---     22-    29+    24     23     26    ---     25  
 24   729 :   14     24     27    ---     26     25    ---     26     31+    31+   ---    ---     25     29     25     23-    27    ---     24  
 25   784 :   15     26     29    ---     27     25-   ---     32     36+    28    ---    ---     25-    32     26     26     31    ---     27  
 26   841 :   15     26-    27    ---     28     27    ---     28     29+    29+   ---    ---     26-    29+    28     28     29+   ---     28  
 27   900 :   15     28-    30    ---     29     28-   ---     31     35     33    ---    ---     28-    38+    29     28-    32    ---     32  

Rank  1: Student 13 with score 113
Rank  2: Student  2 with score 120
=====================================
Rank  3: Student 16 with score 122
Rank  4: Student 15 with score 127
Rank  5: Student  6 with score 128
Rank  6: Student 19 with score 155
Rank  7: Student  8 with score 165
Rank  8: Student  3 with score 178
Rank  9: Student  5 with score 182
Rank 10: Student  9 with score 184
Rank 11: Student 17 with score 207
Rank 12: Student 10 with score 216
Rank 13: Student 14 with score 219
Rank 14: Student  7 with score 6917
Rank 15: Student 18 with score 9423
Rank 16: Student  4 with score 9425
Rank 17: Student 11 with score 9441
Rank 17: Student 12 with score 9441


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