|
Title
|
The deprioritised approach to prioritised algorithms
|
| Author(s) |
Howe, Stephen Alexander, Mathematics & Statistics, Faculty of Science, UNSW
|
| Resource Type |
Thesis
PhD Doctorate
|
| Supervisor(s) |
Greenhill, Catherine, Mathematics & Statistics, Faculty of Science, UNSW
|
| Keyword(s) |
combinatorics
random graphs
algorithms
|
| Date |
2008 |
| Description/Abstract |
Randomised algorithms are an effective method of attacking computationally intractable problems. A simple and fast randomised algorithm may produce results
to an accuracy sufficient for many purposes, especially in the average case. In this
thesis we consider average case analyses of heuristics for certain NP-hard graph optimisation problems. In particular, we consider algorithms that find dominating sets
of random regular directed graphs. As well as providing an average case analysis,
our results also determine new upper bounds on domination numbers of random
regular directed graphs.
The algorithms for random regular directed graphs considered in this thesis are
known as prioritised algorithms. Each prioritised algorithm determines a discrete
random process. This discrete process may be continuously approximated using
differential equations. Under certain conditions, the solutions to these differential
equations describe the behaviour of the prioritised algorithm. Applying such an
analysis to prioritised algorithms directly is difficult. However, we are able to use
prioritised algorithms to define new algorithms, called deprioritised algorithms, that
can be analysed in this fashion.
Defining a deprioritised algorithm based on a given prioritised algorithm, and then
analysing the deprioritised algorithm, is called the deprioritised approach. The
initial theory describing the deprioritised approach was developed by Wormald and
has been successfully applied in many cases. However not all algorithms are covered
by Wormalds theory: for example, algorithms for random regular directed graphs.
The main contribution of this thesis is the extension of the deprioritised approach to
a larger class of prioritised algorithms. We demonstrate the new theory by applying
it to two algorithms which find dominating sets of random regular directed graphs. |
| Language |
EN |
| Rights |
Please click here to view the rights |
| Print Availability |
T/2008/324 (Ask at Level 2 Information Desk, UNSW Library) |
| Citation Link |
Please use this identifier to cite or link to this item: http://handle.unsw.edu.au/1959.4/41753 |
| Full Text | 
|
| Total Attachment(s) | 2 |
List Of Titles
