|
|
My main `pure' interest is in the complexity of counting problems in graph theory. I am especially interested in graph polynomials such as the Tutte polynomial that have some similarities with the chromatic polynomial. The Tutte polynomial is a two variable polynomial encoding a great deal of information about a graph, including the number of spanning trees, spanning forests, acyclic orientations and spanning subsets. Along various curves it specialises to the chromatic polynomial, the reliability polynomial, the Ising and q-state Potts models from statistical physics and the Jones polynomial of an alternating link. A great deal is known about the complexity of evaluating the polynomial at various points or finding the coefficients but there are many challenging open problems related to approximating these quantities.
In a recent paper, Dominic Welsh and I introduced a generalisation of the Tutte polynomial. This polynomial includes a vast range of graph invariants as special cases including the matching polynomial and is equivalent (i.e. contains precisely the same information) as a symmetric function generalisation of the Tutte polynomial introduced by Stanley. It seems likely that there are many more specialisations to be found. One interesting and challenging open question related to this polynomial is whether it determines trees.
A secondary interest is in graphs of bounded tree-width. These graphs have a special structure which ensures that they have small cuts. It is possibly to exploit this property and design fast (often linear time) algorithms for many difficult (NP-hard) graph problems.
A more recent interest of mine is the frequency assignment problem. The radio spectrum is a scarce resource, a problem that is exacerbated by the increasing demand for a wide variety of competing services. The spectrum is divided into channels 1,2,...,n and the problem is to allocate these channels to radio transmitters in such a way as to minimise the use of spectrum. The way in which these channels can be assigned is constrained by the possibility of interference being caused by closely situated transmitters sharing channels. In its simplest form the problem is often considered as a generalisation of the well-known graph colouring problem and many results from this area are useful. A variety of mathematical techniques can be used in this problem, for instance graph colouring and integer programming. Many modern heuristic methods such as the genetic algorithm and tabu search have been used successfully. One particular interest of mine has been applying the concept of domination number to frequency assignment problems. The domination number of an algorithm is a function of the size of the input and gives the number of solutions that the algorithm is guaranteed to bettter. Future research will extend our work on the domination number and examine the L(2,1) labelling problem in which a graph must be labelled so that adjacent vertices must receive labels that differ by at least two and vertices at distance two must receive distinct labels.
I am always extremely pleased to hear from researchers in the field at any level, in particular potential PhD students. Please email me mastsdn@brunel.ac.uk if you are interested in collaboration or doing a PhD. For more information on the Department or Brunel University please see the Brunel website or the Department website.
Back to my home page.
You are (approximately) visitor number
to this page.