Full metadata
Title
Exploration of Algorithms Related to Independent Sets of Steiner Triple Systems
Description
In combinatorial mathematics, a Steiner system is a type of block design. A Steiner triple system is a special case of Steiner system where all blocks contain 3 elements and each pair of points occurs in exactly one block. Independent sets in Steiner triple systems is the topic which is discussed in this thesis. Some properties related to independent sets in Steiner triple system are provided. The distribution of sizes of maximum independent sets of Steiner triple systems of specific order is also discussed in this thesis. An algorithm for constructing a Steiner triple system with maximum independent set whose size is restricted with a lower bound is provided. An alternative way to construct a Steiner triple system using an affine plane is also presented. A modified greedy algorithm for finding a maximal independent set in a Steiner triple system and a post-optimization method for improving the results yielded by this algorithm are established.
Date Created
2021
Contributors
- Wang, Zhaomeng (Author)
- Colbourn, Charles (Thesis advisor)
- Richa, Andrea (Committee member)
- Jiang, Zilin (Committee member)
- Arizona State University (Publisher)
Topical Subject
Resource Type
Extent
52 pages
Language
eng
Copyright Statement
In Copyright
Primary Member of
Peer-reviewed
No
Open Access
No
Handle
https://hdl.handle.net/2286/R.2.N.161428
Level of coding
minimal
Cataloging Standards
Note
Partial requirement for: M.S., Arizona State University, 2021
Field of study: Computer Science
System Created
- 2021-11-16 01:01:33
System Modified
- 2021-11-30 12:51:28
- 3 years ago
Additional Formats