Recent papers, with descriptions or abstracts.

  1. R.E.L. Aldred, B.D. McKay and N.C. Wormald, Small hypohamiltonian graphs, J. Combinatorial Mathematics and Combinatorial Computing 23 (1997), 143-152. Description

  2. M. Molloy, H. Robalewska, R.W. Robinson and N.C. Wormald, 1-factorisations of random regular graphs, Random Structures and Algorithms 10 (1997), 305-321. Abstract

  3. J.H. Rubinstein, D.A. Thomas and N.C. Wormald, Steiner trees for terminals constrained to curves, SIAM J. Discrete Math. 10 (1997), 1-17. Abstract

  4. B.D. McKay and N.C. Wormald, The degree sequence of a random graph. I. The models, Random Structures and Algorithms 11 (1997), 97-117. Abstract

  5. M. Brazil, J.H. Rubinstein, D.A. Thomas, J.F. Weng and N.C. Wormald, Full minimal Steiner trees on lattice sets, J. Combinatorial Theory, Series A 78 (1997), 51-91. Description

  6. M. Brazil, J.H. Rubinstein, D.A. Thomas, J.F. Weng and N.C. Wormald, Minimal Steiner trees for rectangular arrays of lattice points, J. Combinatorial Theory, Series A 79 (1997), 181-208. Description

  7. A. Rucinski and N.C. Wormald, Random graph processes with maximum degree 2, Annals of Applied Probability 7 (1997), 183-199. Abstract

  8. D. Stark and N.C. Wormald, The asymptotic number of d-dimensional convex polygons, J. Combinatorial Theory, Series A 80 (1997), 196-217. Abstract

  9. M. Brazil, J.H. Rubinstein, D.A. Thomas, J.F. Weng and N.C. Wormald, Shortest networks on spheres, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 40 (1998), 453-461. Abstract

  10. T. Lindquester and N.C. Wormald, Factorisation of regular graphs into forests of paths, Discrete Mathematics 186 (1998) 217-226. Abstract

  11. R.E.L. Aldred and N.C. Wormald, Linear k-arboricity of regular graphs, Australasian Journal of Combinatorics 18 (1998), 97-104. Abstract

  12. A. Moffat, O. Petersson and N.C. Wormald, A tree-based mergesort, Acta Informatica 35 (1998), 775--793. Abstract

  13. W.D. Smith and N.C. Wormald, Geometric separator theorems and applications. (Draft manuscript, 50 pages. ps.gz) Abstract

  14. W.D. Smith and N.C. Wormald, Geometric separator theorems and applications. In 39th Annual Symposium on Foundations of Computer Science -- FOCS '98, pages 232--243, Palo Alto, CA, 1998. ( ps.gz) (An abbreviated version of the above.)

  15. A. Knopfmacher, A.M. Odlyzko, B. Pittel, L.B. Richmond, D. Stark, G. Szekeres and N. C. Wormald, The asymptotic number of set partitions with unequal block sizes, Electronic J. Combinatorics 6 (1999), R2 (36 pp). (ps.gz) Abstract

  16. N.C. Wormald, Models of random regular graphs. Surveys in Combinatorics, 1999, J.D. Lamb and D.A. Preece, eds. London Mathematical Society Lecture Note Series, vol 276, pp. 239--298. Cambridge University Press, Cambridge, 1999. ps.gz of preprint. pdf of preprint (A list of corrections and addenda may be found here. ) Abstract

  17. N.C. Wormald, The differential equation method for random graph processes and greedy algorithms, in Lectures on Approximation and Randomized Algorithms (M. Karonski and H.J. Proemel, eds), pp. 73--155. PWN, Warsaw, 1999. (A list of corrections and addenda may be found here. ) Abstract

  18. Z. Gao and N.C. Wormald, The size of the largest components in random planar maps, SIAM J. Discrete Math. 12 (1999), 217--228. Abstract

  19. A. Steger and N.C. Wormald, Generating random regular graphs quickly. Combinatorics, Probab. and Comput. 8 (1999), 377--396. Abstract

  20. W. Duckworth, N.C. Wormald and M. Zito, Approximation algorithms for finding sparse 2-Spanners of 4-Connected planar triangulations, in Proc. Tenth Australasian Workshop on Combinatorial Algorithms, R.J. Simpson and R. Raman eds., Curtin University, Perth, pp. 63--75 (1999). (ps.gz of preprint) Abstract

  21. A. Telcs and N.C. Wormald, Branching and tree indexed random walks on fractals, J. Applied Probab. 36 (1999), 999--1011. Abstract

  22. M. Ng, M. Steel and N.C. Wormald, The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees, Discrete Applied Mathematics 98 (2000), 227--235. Abstract

  23. Z. Gao and N.C. Wormald, The distribution of the maximum vertex degree in random planar maps, J. Combinatorial Theory, Series A 89 (2000), 201--230. Abstract

  24. H.D. Robalewska and N.C. Wormald, Random star processes, Combinatorics, Probability and Computing 9 (2000), 33--43. Abstract

  25. H. Assiyatun and N.C. Wormald, Covering regular graphs with forests of small trees, Australasian Journal of Combinatorics 22 (2000), 219--226. Abstract

  26. M. Brazil, D. Lee, J.H. Rubinstein, D.A. Thomas, J.F. Weng and N.C. Wormald, Network optimisation of underground mine designs, Proc. Australasian Inst. of Mining and Metallurgy 305 (2000), 57--65. Abstract

  27. J.H. Kim and N.C. Wormald, Random matchings which induce Hamilton cycles, and hamiltonian decompositions of random regular graphs, J. Combinatorial Theory, Series B 81 (2001), 20--44. (pdf of preprint) Abstract

  28. I.M. Wanless and N.C. Wormald, Regular graphs with no homomorphisms onto cycles, J. Combinatorial Theory, Series B 82 (2001), 155--160. (ps.gz of preprint) Abstract

  29. R.W. Robinson and N.C. Wormald, Hamilton cycles containing randomly selected edges in random regular graphs, Random Structures and Algorithms 19 (2001), 128-147. (pdf of preprint) Abstract

  30. J.H. Rubinstein, D.A. Thomas and N. C. Wormald, A polynomial algorithm for a constrained travelling salesman problem, Networks 38 (2001), 68--75. (ps.gz of preprint) Abstract

  31. Z. Gao, I.M. Wanless and N.C. Wormald, Counting 5-connected planar triangulations, J. Graph Theory 38 (2001), 18--35. Abstract

  32. M. Krivelevich, B. Sudakov, V. Vu and N.C. Wormald, Random regular graphs of high degree, Random Structures and Algorithms 18 (2001), 346--363. Abstract

  33. N. Alon, V.J. Teague and N.C. Wormald, Linear arboricity and linear k-arboricity of regular graphs, Graphs and Combinatorics 17 (2001), 11--16. (ps.gz of preprint) Abstract

  34. M. Brazil, J.H. Rubinstein, D.A. Thomas, J.F. Weng and N.C. Wormald, Gradient-constrained minimum networks I: Fundamentals, J. Global Optim. 21 (2001), 139--155. (ps.gz of preprint) Abstract

  35. A. Rucinski and N.C. Wormald, Connectedness of graphs generated by a random d-process, (preprint). J. Austral. Math. Soc. 72 (2002), 67--85. (ps.gz of preprint) Abstract

  36. Z. Gao and N.C. Wormald, Enumeration of rooted cubic planar maps, Annals of Combinatorics (in press). (ps.gz) Abstract

  37. W. Duckworth, N.C. Wormald and M. Zito, A PTAS for a sparsest 2-spanner of a 4-connected planar triangulation, Journal of Discrete Algorithms (in press). Abstract

  38. W. Duckworth, N.C. Wormald and M. Zito, Maximum induced matchings of random cubic graphs, Sixth Annual International Computing and Combinatorics Conference (COCOON 2000) (in press). (ps.gz) Abstract

  39. W. Duckworth, N.C. Wormald and M. Zito, Maximum induced matchings of random cubic graphs,Journal of Computational and Applied Mathematics (in press). (A more polished version of the paper with the same title above (#28).) ps.gz

  40. Z. Gao and N.C. Wormald, Sharp concentration of the number of submaps in random planar triangulations, Combinatorica (in press). Abstract

  41. B.D. McKay, I.M. Wanless and N.C. Wormald, Asymptotic enumeration of graphs with a given upper bound on the maximum degree, Combinatorics, Probability and Computing (in press). (ps.gz) Description

  42. M. Krivelevich, B. Sudakov, V. Vu and N.C. Wormald, On the probability of independent sets in random graphs, Random Structures and Algorithms (in press). (pdf) Abstract

  43. R. Castelo and N.C. Wormald Enumeration of P_4-free chordal graphs, Graphs and Combinatorics (in press). (pdf) Abstract

  44. N.C. Wormald Analysis of greedy algorithms on graphs with bounded degrees, Discrete Mathematics (in press). (pdf) Abstract

  45. C.S. Greenhill, A. Rucinski and N.C. Wormald Connectivity of the random star process, Combinatorics, Probability and Computing (in press). (pdf) Abstract

  46. W. Duckworth and N.C. Wormald, Minimum independent dominating sets of random cubic graphs, Random Structures and Algorithms (in press). Abstract

  47. E.A. Bender, Z. Gao and N.C. Wormald, The number of labeled 2-connected planar graphs, preprint. Abstract

  48. Z. Gao and N.C. Wormald, Asymptotic normality determined by high moments, and submap counts of random maps, preprint. (pdf) Abstract

  49. C.S. Greenhill, S. Janson, J. H. Kim, and N.C. Wormald, Permutation graphs and contiguity, preprint. (pdf) Abstract

  50. W. Duckworth and N.C. Wormald, Linear programming and the worst-case analysis of greedy algorithms on cubic graphs, preprint. (pdf) Abstract

  51. J. Nesetril and N.C. Wormald, The acyclic edge chromatic number of a random d-regular graph is d+1, preprint. (ps) Abstract

  52. A. Frieze and N.C. Wormald, Random k-SAT: A tight threshold for moderately growing k, preprint. (pdf) Description

  53. S. Bau, N.C. Wormald and S.M. Zhou, Decycling numbers of random regular graphs, preprint. (pdf) Abstract

  54. M. Brazil, D. Lee, J.H. Rubinstein, D.A. Thomas, J.F. Weng and N.C. Wormald, A network model to optimise cost in underground mine design, preprint.

  55. C.S. Greenhill and J.H. Kim and N.C. Wormald, Hamiltonian decompositions of random bipartite regular graphs, preprint.

  56. J. Diaz, N. Do, M. Serna and N.C. Wormald, Bisection of random cubic graphs, preprint.

  57. B. Pittel and N.C. Wormald, Asymptotic enumeration of sparse graphs with a minimum degree constraint, preprint.

This page, its contents and style, are the responsibility of the author and do not represent the views, policies or opinions of The University of Melbourne. Last updated by Nick Wormald 4/06/02.