Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-23T03:01:24.321Z Has data issue: false hasContentIssue false
  • English
  • Français

THE DEPRIORITISED APPROACH TO PRIORITISED ALGORITHMS

Part of: Algorithms - Computer Science Graph theory

Published online by Cambridge University Press:  14 May 2009

STEPHEN HOWE
STEPHEN HOWE*
Affiliation:
Centre for Mathematics and its Applications, Mathematical Sciences Institute, Australian National University, Canberra, ACT 0200, Australia (email: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

An abstract is not available for this content so a preview has been provided. As you have access to this content, a full PDF is available via the ‘Save PDF’ action button.
Image of the first page of this content. For PDF version, please use the ‘Save PDF’ preceeding this image.'

Keywords

randomised algorithmsdeprioritised algorithmsrandom regular digraphsdominating sets

MSC classification

Secondary: 05C80: Random graphs 68W20: Randomized algorithms 05C69: Dominating sets, independent sets, cliques
Type
PhD thesis
Information
Bulletin of the Australian Mathematical Society , Volume 79 , Issue 3 , June 2009 , pp. 523 - 524
Copyright
Copyright © Australian Mathematical Society 2009

Footnotes

Thesis submitted to The University of New South Wales, September 2008. Degree approved, January 2008. Supervisor: Dr Catherine Greenhill.

References

[1] Beis, M., Duckworth, W. and Zito, M., ‘Packing vertices and edges in random regular graphs’, Random Structures Algorithms 32 (2008), 20–37.CrossRefGoogle Scholar
[2] Diaz, J., Serna, M. and Wormald, N. C., ‘Bounds on the bisection width for random d-regular graphs’, Theoret. Comput. Sci. 382 (2007), 120–130.CrossRefGoogle Scholar
[3] Duckworth, W. and Wormald, N. C., ‘On the independent domination number of random regular graphs’, Combin. Probab. Comput. 15 (2006), 513–522.CrossRefGoogle Scholar
[4] Wormald, N. C., ‘The differential equation method for random graph processes and greedy algorithms’, in: Lectures on Approximation and Randomized Algorithms (Polish Scientific Publishers PWN, Warsaw, 1999), pp. 73–155.Google Scholar
[5] Wormald, N. C., ‘Analysis of greedy algorithms on graphs with bounded degrees’, Discrete Math. 273 (2003), 235–260.CrossRefGoogle Scholar