Breadcrumb

 
 

In solving the dominating set problem : group theory approach

Title:

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.

[img]
Preview
PDF
7Mb

Abstract

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 > Faculty 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:Theses (Ph.D.)
Program:Computer Science and Software Engineering
Date:1998
Thesis Supervisor(s):Lam, Clement
ID Code:478
Deposited By:Concordia University Libraries
Deposited On:27 Aug 2009 13:12
Last Modified:08 Dec 2010 10:14
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

Document Downloads

More statistics for this item...

Concordia University - Footer