Login | Register

In solving the dominating set problem : group theory approach


In solving the dominating set problem : group theory approach

Ma, Ka Leung (1998) In solving the dominating set problem : group theory approach. PhD thesis, Concordia University.

[thumbnail of NQ40311.pdf]
Text (application/pdf)


This thesis presents a new way to find the dominating set of a graph by introducing the concept of an orbit graph and a weighted dominating set. We showed that the Blokhuis-Lam method for the football pool problem is a special case of assuming that the solution has a non-trivial automorphism group. A general purpose algorithm for solving the dominating set problem is developed by using a coverage test, a wastage test, and the orbit and block structure of the graph's symmetry group to prune the search. The algorithm has been implemented and the program can be used to find all the dominating sets of any undirected, loopless, and labeled graph or all the weighted dominating sets of an orbit graph. The program analyzed grid graphs and football pool graphs, and was able to find the minimum dominating sets of any m x n grid graph for m X 10 and n X 11. For the football pool problem, we have determined that the automorphism group of n matches is S 3 [Special characters omitted.] S n and the automorphism group of a rook domain graph w n,q is S q [Special characters omitted.] S n . We also applied the orbit graph transformation to the football pool problem of 5, 6 and 7 matches. By considering only cyclic subgroups up to conjugacy, we generated 107 orbit graphs for the case of 5 matches, 220 orbit graphs for 6 matches and 428 orbit graphs for 7 matches. Using our program, we found dominating sets for 5 matches with size 27. For more matches, we found no better bounds within the limitations of our implementation. However, by using the mixed integer optimizer in the linear programming package CPLEX, we found weighted dominating sets, and hence, dominating sets matching the best known upper bounds. They also have more symmetry than the known solutions. There is hope that some of the unsolved orbit graphs can lead to smaller dominating sets.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (PhD)
Authors:Ma, Ka Leung
Pagination:ix, 108, 70 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:Ph. D.
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Lam, Clement
Identification Number:QA 164 M15 1998
ID Code:478
Deposited By: Concordia University Library
Deposited On:27 Aug 2009 17:12
Last Modified:13 Jul 2020 19:46
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top