Classification Algorithms for Codes and Designs (Algorithms and Computation in Mathematics)

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

Author(s): Petteri Kaski, Patric R.J. Ostergard,
Series: Algorithms and Computation in Mathematics
Edition: 1
Publisher: Springer
Year: 2005

Language: English
Pages: 425

Cover......Page 1
Algorithms and Computation in Mathematics, Volume 15......Page 2
Classification Algorithms for Codes and Designs......Page 4
9783540289906......Page 5
Contents......Page 6
Preface......Page 10
1 Introduction......Page 14
2.1 Graphs......Page 20
2.2 Designs......Page 26
2.2.1 Incidence Structures......Page 27
2.2.2 t-Designs......Page 29
2.2.3 Balanced Incomplete Block Designs......Page 31
2.2.4 Steiner Triple Systems......Page 33
2.2.5 Some Other Families of Designs......Page 34
2.2.6 Resolutions of Designs......Page 35
2.3.1 Preliminaries......Page 39
2.3.2 Equidistant Codes......Page 42
2.3.3 Linear Codes......Page 46
2.3.4 Equivalence of Codes......Page 48
2.4.1 Orthogonal Arrays......Page 50
2.4.2 Latin Squares......Page 52
2.4.3 Hadamard Matrices......Page 56
3 Representations and Isomorphism......Page 60
3.1 Finite Groups and Group Actions......Page 61
3.1.1 Permutation Groups......Page 63
3.1.2 Group Actions......Page 66
3.1.3 Isomorphism and the Orbit-Stabilizer Theorem......Page 68
3.1.4 Semidirect and Wreath Products......Page 72
3.2 Categories and Equivalence......Page 77
3.2.1 Automorphisms and the Automorphism Group......Page 80
3.2.2 Functors......Page 83
3.2.3 Reconstructibility and Equivalence of Categories......Page 89
3.3 Isomorphism Computations......Page 94
3.3.1 Lexicographic Order......Page 95
3.3.2 Representing Objects as Colored Graphs......Page 96
3.3.3 Invariants and Certificates......Page 101
3.3.4 Subobject Invariants......Page 104
3.3.5 Compounding and Iterative Refinement......Page 108
3.3.6 Isomorphism Problems and Tools......Page 114
4.1 Exhaustive Generation......Page 118
4.1.1 Searching and Search Trees......Page 119
4.1.2 Backtrack Search......Page 122
4.1.3 Estimating Resource Requirements......Page 125
4.2 Techniques for Isomorph Rejection......Page 127
4.2.1 Recorded Objects......Page 130
4.2.2 Orderly Generation......Page 133
4.2.3 Canonical Augmentation......Page 137
4.2.4 Homomorphisms of Group Actions and Localization......Page 146
5 Auxiliary Algorithms......Page 158
5.1 Clique Algorithms......Page 159
5.2 Exact Cover Algorithms......Page 162
5.3 Set Cover Algorithms......Page 165
5.4 Diophantine Linear Systems of Equations......Page 168
5.5 Permutation Group Algorithms......Page 172
5.6 Isomorphism Algorithms......Page 177
5.7 Distributing Computer Search......Page 184
6.1.1 Classification Point by Point......Page 188
6.1.2 Testing Canonicity of Incidence Matrices......Page 195
6.1.3 Classification Block by Block......Page 200
6.1.4 Isomorph Rejection for Designs Extending a Seed......Page 206
6.1.5 Tailored Approaches......Page 208
6.1.6 Results......Page 210
6.2.1 Classification Point by Point......Page 216
6.2.2 Classification Block by Block......Page 218
6.2.3 Results......Page 220
6.3 Resolutions of Designs......Page 221
6.3.1 Classification via the Underlying Design......Page 222
6.3.2 Direct Classification......Page 223
6.3.3 Results......Page 224
6.4 Designs with Additional Properties......Page 228
7.1 Error-Correcting Codes......Page 232
7.1.1 Classification via Subcodes......Page 233
7.1.2 Classification Codeword by Codeword......Page 236
7.1.3 Constant Weight Codes......Page 241
7.1.4 Results......Page 242
7.2 Covering Codes......Page 247
7.2.1 Some Basic Approaches......Page 248
7.2.2 Stepwise Refinement of Hamming Spaces......Page 250
7.2.3 Further Improvements......Page 252
7.2.4 Isomorph Rejection......Page 253
7.2.5 Constant Weight Covering Codes......Page 254
7.2.6 Results......Page 255
7.3.1 Equivalence of Linear Codes......Page 259
7.3.2 Constructing Linear Codes via Subcodes......Page 260
7.3.3 Isomorph Rejection using Words of Given Weights......Page 262
7.3.4 Isomorph Rejection in Projective Geometries......Page 263
7.3.5 Implementation Issues......Page 266
7.3.6 Results......Page 268
8.1 Triple Systems......Page 272
8.1.1 One-Factorizations of Complete Graphs......Page 273
8.1.2 Group Divisible Designs with Block Size 3......Page 276
8.1.3 Latin Squares......Page 277
8.2 Hadamard Matrices......Page 278
8.3 Orthogonal Arrays......Page 281
9 Prescribing Automorphism Groups......Page 286
9.1 Preliminaries......Page 287
9.2 Designs......Page 290
9.2.1 The Kramer–Mesner Method......Page 291
9.2.2 Tactical Decompositions......Page 294
9.2.3 Example: STSs with Nontrivial Groups......Page 297
9.2.4 Some Results......Page 302
9.3.1 Covering Codes......Page 304
9.3.2 Error-Correcting Codes......Page 305
9.3.3 The Matrix Method......Page 306
9.3.4 Linear Codes......Page 307
9.4 Other Objects......Page 308
10 Validity of Computational Results......Page 310
10.1 Errors and Remedies......Page 311
10.2 Double Counting Using the Orbit-Stabilizer Theorem......Page 312
10.3 Double Counting by Identifying Subobjects......Page 314
10.4 Some Final Observations......Page 318
11.1 Preliminaries......Page 320
11.2 Completion Problems......Page 327
11.3 Isomorphism Problems......Page 336
11.4 Classification Problems......Page 343
12.1 Projective Planes of Order 10......Page 352
12.2 Codes of Designs......Page 354
12.3.1 There are No Codewords of Weight 12......Page 358
12.3.2 There are No Codewords of Weight 15......Page 361
12.3.3 There are No Codewords of Weight 16......Page 364
12.3.4 There are No Codewords of Weight 19......Page 368
References......Page 378
Problem Index......Page 412
Index......Page 414