Algorithms for random r-in r-out directed graphs
Dr Stephen Howe (ANU)
MSI Advanced Computational Mathematics SeminarDATE: 2009-03-23
TIME: 11:00:00 - 12:00:00
LOCATION: John Dedman, G35
CONTACT: JavaScript must be enabled to display this email address.
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 talk I will describe a class of randomised algorithms, called deprioritised algorithms, for random r-in r-out directed graphs. The analysis of such algorithms determines properties of random r-in r-out directed graphs, and can also provide average case analyses of heuristic algorithms for NP-hard graph optimisation problems.
Deprioritised algorithms are based on similar algorithms known as prioritised algorithms. Wormald introduced deprioritised algorithms to avoid difficulties in analysing prioritised algorithms. As an example, I will introduce a prioritised algorithm that finds a 2-path dominating set of a random r-in r-out directed graph. (A 2-path dominating set is similar to a dominating set of an undirected graph.) Then I will show how to define and analyse a deprioritised algorithm based on a given prioritised algorithm. Perhaps surprisingly, the analysis of the deprioritised algorithm requires the solution of a system of differential equations. The solution of system of differential equations for the algorithm mention above determines new upper bounds on the 2-path domination numbers of random r-in r-out directed graphs.
BIO:
http://wwwmaths.anu.edu.au/~howe/
