Finding Sequence of Graceful Graphs Using Parallel Computing
Name
Miron Storožev
Abstract
Describing graceful graphs is one of many unsolved problems in graph theory. One option to describe graphs is to use their integer sequence. So far, describing graceful graphs using its number sequence was unattainable, since sequence was not long enough to make any conclusions based on it.
The program, that finds number of graceful graphs with n vertices, already exists, but its time consumption caused by large computational complexity made counting graceful graphs with more than 11 vertices almost impossible.
The aim of this bachelor’s thesis is to optimise existing graceful graphs counting program by using parallel computing. Optimised program was run on cluster to count graceful graphs with 12 and 13 vertices.
Optimised program can be used to count graceful graphs with even higher number of vertices. Numbers of graceful graphs with vertex number of 12 and 13 are added to number sequence and will be used to describe graceful graphs.
The program, that finds number of graceful graphs with n vertices, already exists, but its time consumption caused by large computational complexity made counting graceful graphs with more than 11 vertices almost impossible.
The aim of this bachelor’s thesis is to optimise existing graceful graphs counting program by using parallel computing. Optimised program was run on cluster to count graceful graphs with 12 and 13 vertices.
Optimised program can be used to count graceful graphs with even higher number of vertices. Numbers of graceful graphs with vertex number of 12 and 13 are added to number sequence and will be used to describe graceful graphs.
Graduation Thesis language
Estonian
Graduation Thesis type
Bachelor - Computer Science
Supervisor(s)
Ahti Peder
Defence year
2018