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

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.
Reuse Permissions
  • Downloads
    PDF (2.3 MB)
    Download count: 1

    Details

    Title
    • Exploration of Algorithms Related to Independent Sets of Steiner Triple Systems
    Contributors
    Date Created
    2021
    Subjects
    Resource Type
  • Text
  • Collections this item is in
    Note
    • Partial requirement for: M.S., Arizona State University, 2021
    • Field of study: Computer Science

    Machine-readable links