Advanced search options

Sorted by: relevance · author · university · date | New search

You searched for `subject:(isomorph rejection)`

.
Showing records 1 – 2 of
2 total matches.

▼ Search Limiters

1. Kaski, Petteri. Algorithms for Classification of Combinatorial Objects.

Degree: 2005, Helsinki University of Technology

URL: http://lib.tkk.fi/Diss/2005/isbn9512277271/

A recurrently occurring problem in combinatorics is the need to completely characterize a finite set of finite objects implicitly defined by a set of constraints. For example, one could ask for a list of all possible ways to schedule a football tournament for twelve teams: every team is to play against every other team during an eleven-round tournament, such that every team plays exactly one game in every round. Such a characterization is called a classification for the objects of interest. Classification is typically conducted up to a notion of structural equivalence (isomorphism) between the objects. For example, one can view two tournament schedules as having the same structure if one can be obtained from the other by renaming the teams and reordering the rounds. This thesis examines algorithms for classification of combinatorial objects up to isomorphism. The thesis consists of five articles – each devoted to a specific family of objects – together with a summary surveying related research and emphasizing the underlying common concepts and techniques, such as backtrack search, isomorphism (viewed through group actions), symmetry, isomorph rejection, and computing isomorphism. From an algorithmic viewpoint the focus of the thesis is practical, with interest on algorithms that perform well in practice and yield new classification results; theoretical properties such as the asymptotic resource usage of the algorithms are not considered. The main result of this thesis is a classification of the Steiner triple systems of order 19. The other results obtained include the nonexistence of a resolvable 2-(15, 5, 4) design, a classification of the one-factorizations of k-regular graphs of order 12 for k ≤ 6 and k = 10, 11, a classification of the near-resolutions of 2-(13, 4, 3) designs together with the associated thirteen-player whist tournaments, and a classification of the Steiner triple systems of order 21 with a nontrivial automorphism group.

Research reports / Helsinki University of Technology, Laboratory for Theoretical Computer Science, ISSN 1457-7615; 94

Subjects/Keywords: classification algorithm; isomorphism; isomorph rejection; near-resolvable design; one-factorization; orderly algorithm; regular graph; resolvable design; Steiner triple system

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Kaski, P. (2005). Algorithms for Classification of Combinatorial Objects. (Thesis). Helsinki University of Technology. Retrieved from http://lib.tkk.fi/Diss/2005/isbn9512277271/

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Kaski, Petteri. “Algorithms for Classification of Combinatorial Objects.” 2005. Thesis, Helsinki University of Technology. Accessed September 22, 2020. http://lib.tkk.fi/Diss/2005/isbn9512277271/.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Kaski, Petteri. “Algorithms for Classification of Combinatorial Objects.” 2005. Web. 22 Sep 2020.

Vancouver:

Kaski P. Algorithms for Classification of Combinatorial Objects. [Internet] [Thesis]. Helsinki University of Technology; 2005. [cited 2020 Sep 22]. Available from: http://lib.tkk.fi/Diss/2005/isbn9512277271/.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Kaski P. Algorithms for Classification of Combinatorial Objects. [Thesis]. Helsinki University of Technology; 2005. Available from: http://lib.tkk.fi/Diss/2005/isbn9512277271/

Not specified: Masters Thesis or Doctoral Dissertation

2. Haanpää, Harri. Constructing Certain Combinatorial Structures by Computational Methods.

Degree: 2004, Helsinki University of Technology

URL: http://lib.tkk.fi/Diss/2004/isbn9512269422/

Combinatorics is a branch of mathematics that generally deals with a finite or at most countably infinite set and collections of its subsets. These collections must then satisfy certain criteria depending on the class of objects and the problem being considered. The most fundamental problem in combinatorics is the problem of existence: Does a combinatorial structure that satisfies the given requirements exist? In general, it is straightforward to verify that a proposed structure satisfies the required criteria, but finding a structure of the required type is difficult. If a structure of the required type exists, any method that constructs one is sufficient to settle the existence question. Two problems closely related to the existence problem are the enumeration problem – how many different combinatorial structures of the required type exist – and the optimization problem – which combinatorial structure of the required type is the best, judged by some criterion. A computer may be very useful in solving problems of the three types mentioned above. If it is suspected that a structure of the required kind exists, one may design a computer program to sample the space of possible structures until one that satisfies the criteria is found. To show the nonexistence of a structure, to enumerate the structures of a given kind, or to determine the best structure of a given kind, it is generally necessary to conduct a case-by-case analysis of all possible structures, which is a task for which a computer is especially suited. It is, however, often a nontrivial task to design an efficient algorithm for such an analysis. In this thesis several ways of applying computational methods to combinatorial problems are described. Tabu search on graphs with cyclic symmetry is used to obtain a lower bound for a Ramsey number, an orderly backtrack search with isomorph rejection is applied to a particular class of codes to classify certain designs and the whist tournaments with up to thirteen players, and another orderly search is used to obtain the optimal sum and difference packings and covers of small Abelian groups.

Research reports / Helsinki University of Technology, Laboratory for Theoretical Computer Science. A, ISSN 1457-7615; 89

Subjects/Keywords: balanced incomplete block design; difference cover; difference packing; isomorph rejection; orderly algorithm; Ramsey number; Sidon set; sum cover; sum packing; whist tournament

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Haanpää, H. (2004). Constructing Certain Combinatorial Structures by Computational Methods. (Thesis). Helsinki University of Technology. Retrieved from http://lib.tkk.fi/Diss/2004/isbn9512269422/

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Haanpää, Harri. “Constructing Certain Combinatorial Structures by Computational Methods.” 2004. Thesis, Helsinki University of Technology. Accessed September 22, 2020. http://lib.tkk.fi/Diss/2004/isbn9512269422/.

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Haanpää, Harri. “Constructing Certain Combinatorial Structures by Computational Methods.” 2004. Web. 22 Sep 2020.

Vancouver:

Haanpää H. Constructing Certain Combinatorial Structures by Computational Methods. [Internet] [Thesis]. Helsinki University of Technology; 2004. [cited 2020 Sep 22]. Available from: http://lib.tkk.fi/Diss/2004/isbn9512269422/.

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Haanpää H. Constructing Certain Combinatorial Structures by Computational Methods. [Thesis]. Helsinki University of Technology; 2004. Available from: http://lib.tkk.fi/Diss/2004/isbn9512269422/

Not specified: Masters Thesis or Doctoral Dissertation