Recent papers, with descriptions or abstracts.
Chronologically:
Topics (recently published papers):
Preprints
- C. Hoppen and N. Wormald.
Local algorithms, regular graphs of large girth, and random regular
graphs, accepted for publication.
- P. Pralat and N. Wormald.
Almost all 5-regular graphs have a 3-flow, preprint.
- P. Pralat and N. Wormald.
Meyniel's conjecture holds for random regular graphs, preprint.
- A. Coja-Oghlan and N. Wormald.
The number of satisfying assignments of random regular k-sat
formulas, preprint.
- D. Stark and N.C. Wormald.
The probability of nonexistence of a subgraph in a moderately sparse
random graph, preprint.
- P. Gao and N. Wormald.
Uniform generation of random graphs with power-law degree sequences, preprint.
- N.C. Wormald, Tournaments with many Hamilton cycles, preprint.
(pdf)
Abstract
BACK to top
Random Graphs and Structures
- E. Lubetzky, J. Kahn and N. Wormald,
Cycle factors and renewal theory, preprint.
Communications in Pure and Applied Mathematics
70 (2017) 289-339.
- E. Lubetzky, J. Kahn and N. Wormald,
The threshold for combs in random graphs,
Random Structures and Algorithms
48 (2016), 794-802.
- C. Hoppen and N. Wormald,
Local algorithms, regular graphs of large girth, and random regular graphs,
J. Combinatorial Theory, Series B
121 (2016), 367-397.
- P. Pralat and N. Wormald,
Meyniel's conjecture holds for random graphs,
Random Structures and Algorithms
48 (2016), 396-421.
-
P. Gao and N. Wormald,
Orientability thresholds for random hypergraphs,
Combinatorics, Probability and Computing
24 (2015), 774-824.
(pdf)
Abstract
- I. Benjamini, G. Kozma and N. Wormald,
The mixing time of the giant component of a random graph,
Random Structures and Algorithms
45 (2014), 383-407.
- X. Perez-Gimenez and N. Wormald,
Asymptotic enumeration of strongly connected digraphs by vertices and edges,
Random Structures and Algorithms
43 (2013), 80-114.
(pdf)
Abstract
- G.Kemkes, C.M. Sato and N. Wormald,
Asymptotic enumeration of sparse 2-connected graphs,
Random Structures and Algorithms
43 (2013), 354-376.
(pdf)
Abstract
- A. Mehrabian and N. Wormald,
On the Stretch Factor of Randomly Embedded Random Graphs,
Discrete and Computational Geometry
49 (2013), 647-658.
-
P. Gao and N. Wormald,
Orientability thresholds for random hypergraphs,
manuscript.
(pdf)
Abstract
- G. Kemkes and N. Wormald,
An improved upper bound on the length of the longest cycle of a post-critical random graph,
SIAM J. Discrete Math.
27 (2013), 342-362.
(pdf)
Abstract
- P. Gao, Y. Su and N. Wormald,
Induced subgraphs in sparse random graphs with given degree sequence,
European Journal of Combinatorics
33 (2012), 1142-1166.
(pdf)
Abstract
- F.C. Botelho, N. Wormald and N. Ziviani,
Cores of Random r-Partite Hypergraphs,
Information Processing Letters
112 (2012), 314-319.
- T. Muller, X. Perez-Gimenez and N. Wormald,
Disjoint Hamilton cycles in the random geometric graph,
J. Graph Theory
68 (2011), 299-322.
- M. Krivelevich, B. Sudakov and N. Wormald,
Regular induced subgraphs of a random graph,
Random Structures and Algorithms
38 (2011), 235-250.
- P. Pralat, J. Verstraete and N. Wormald,
On the threshold for k-regular subgraphs of random graphs,
Combinatorica.
31 (2011), 565-581.
(pdf)
Abstract
-
O. Riordan and N. Wormald,
The diameter of sparse random graphs,
Combinatorics, Probability and Computing
19 (2010), 835-926.
(pdf)
Abstract
- P. Gao and N. Wormald,
Load balancing and orientability thresholds for random hypergraphs,
Proceedings of STOC (ACM)
(2010), 97-104. (The journal version of this paper is "Orientability thresholds for random hypergraphs", listed above.)
(pdf)
Abstract
-
N.C. Wormald and S. Zhou,
Large forbidden trade volumes of random graphs,
Discrete Mathematics
308 (2008), 2751-2755.
(pdf)
Abstract
- J. Cain, P. Sanders and N. Wormald, The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation,
Proceedings of 18th Annual ACM-SIAM SODA 469-476 (2007).
(pdf)
Abstract
- J. Cain and N. Wormald, Encores on cores,
Electronic Journal of Combinatorics
13 (2006), Research Paper 81, 13 pp.
(corrected pdf) (erratum for published version)
Abstract
-
N.C. Wormald, Random graphs and asymptotics,
Chapter 8.2 in Handbook of Graph Theory (J.L. Gross and J. Yellen,
eds.). Chapter 8.2, pp. 817-836. CRC, Boca Raton, 2004.
Description
(Can't find one of the references? Correction to published version.)
- A. Frieze and N.C. Wormald, Random k-SAT: A tight
threshold for moderately growing k, Combinatorica
25 (2005), 297-305. (pdf)
Abstract
-
B. Pittel and N.C. Wormald, Counting connected
graphs inside-out,
J. Combinatorial Theory, Series B
93 (2005), 127-172.
(pdf)
Abstract
-
M. Krivelevich, B. Sudakov, V. Vu and N.C.
Wormald, On the probability of independent sets in random graphs, Random
Structures and Algorithms 22 (2003), 1-14.
(pdf)
Abstract
- 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.
(ps.gz)
Abstract
-
N.C. Wormald,
The perturbation method for triangle-free random graphs,
Random Structures and Algorithms
9 (1996), 253-270.
(pdf)
Abstract
-
B. Pittel, J. Spencer and N.C. Wormald,
Sudden emergence of a giant $k$-core in a random graph,
J. Combinatorial Theory, Series B
67 (1996), 111-151.
(pdf)
Abstract
BACK to top
Random Regular Graphs
- P. Gao and N. Wormald.
Uniform generation of random regular graphs,
SIAM J. Computing
46 (2017) 1395--1427.
- L. Kang and N. Wormald,
Minimum power dominating sets of random cubic graphs,
J. Graph Theory
85 (2017) 152-171.
- E. Lubetzky, J. Kahn and N. Wormald,
Cycle factors and renewal theory, preprint.
Communications in Pure and Applied Mathematics
70 (2017) 289-339.
-
P. Gao and N. Wormald,
Uniform generation of random regular graphs,
In Proceedings of 2015 IEEE 56th Annual Symposium on Foundations
of Computer Science (FOCS)
(2015), 1218--1230.
- B. Kolesnik and N. Wormald,
Lower bounds for the isoperimetric numbers of random regular graphs,
SIAM J. Discrete Math.
428 (2014), 553-575.
- I. Benjamini, C. Hoppen, E. Ofek, P. Pralat and N. Wormald,
Geodesics and almost geodesic cycles in random regular graphs,
J. Graph Theory
66 (2011), 115-136.
- G. Kemkes, X. Perez-Gimenez and N. Wormald,
On the chromatic number of random d-regular graphs,
Advances in Mathematics
223 (2010), 300-328.
(pdf)
Abstract
- J. Diaz, A.C. Kaporis, G.D. Kemkes, L.M. Kirousis, X. Perez and N. Wormald,
On the chromatic number of random 5-regular graphs,
J. Graph Theory
61 (2009), 157-191.
(pdf)
Abstract
- N. Alon , P. Pralat and N. Wormald,
Cleaning d-regular graphs with brushes,
SIAM J. Discrete Math.
23 (2008), 233-250.
(pdf)
Abstract
- C.S. Greenhill, F.B. Holt and N. Wormald,
Expansion properties of a random regular graph after random vertex deletions,
Europ. J. Combin.
29 (2008), 1139-1150.
(pdf)
Abstract
- Z. Gao and N. Wormald,
Distribution of subgraphs of random regular graphs,
Random Structures and Algorithms
32 (2008), 38-48.
(pdf)
Abstract
- M.-E. Messinger, R.J. Nowakowski, P. Pralat and N. Wormald,
Cleaning random d-regular graphs with brushes using a degree-greedy algorithm,
in CAAN 2007, Lecture Notes in Computer Science
4852 (2007), 13-26.
(pdf)
Abstract
- S. Janson and N. Wormald,
Rainbow Hamilton cycles in random regular graphs,
Random Structures and Algorithms
30 (2007), 35-49.
(pdf)
Abstract
- J. Diaz, M. Serna, and N.C. Wormald, Computation of the bisection
width for random d-regular graphs,
Theoretical Computer Science
382 (2007), 120-130.
(pdf)
Abstract
- L. Shi and N. Wormald, Colouring random regular graphs,
Combinatorics, Probability and Computing
16 (2007), 459-494.
(pdf)
Abstract
- L. Shi and N. Wormald, Colouring random 4-regular graphs, Combinatorics, Probability and Computing
16 (2007), 309-344.
(pdf)
Abstract
- H. Assiyatun and N. Wormald,
3-star factors in random regular graphs,
, Europ. J. Combinatorics 27 (2006), 1249-1262.
(pdf)
Abstract
- S. Gerke, C. Greenhill and N. Wormald,
The generalised acyclic edge chromatic number of random regular graphs , J. Graph Theory 53 (2006), 101-125.
(pdf)
Abstract
- W. Duckworth and N.C. Wormald,
On the independent domination
number of random regular graphs, Combinatorics, Probability
and Computing 15 (2006), 513-522. (pdf)
Abstract
- J. Nesetril and N.C. Wormald, The acyclic edge chromatic number
of a random d-regular graph is d+1, J. Graph Theory
49 (2005), 69-74. (ps)
Abstract
- B.D. McKay, N.C. Wormald, and B. Wysocka, Short cycles
in random regular graphs, Electronic Journal of Combinatorics 11 (2004), RP 66, 12 pp.
(pdf)
Abstract
- C.S. Greenhill and J.H. Kim and N.C. Wormald, Hamiltonian decompositions
of random bipartite regular graphs, J. Combinatorial Theory,
Series B 90 (2004), 195-222.
(pdf)
Abstract
Computation of the bisection width for random d-regular
graphs.
In LATIN 2004: Theoretical informatics, Lecture Notes in Computer Science
2976 , pp. 49-58, Springer, 2004.
(See journal version above.)
- N.C. Wormald Analysis of greedy algorithms
on graphs with bounded degrees, , EuroComb '01 (Barcelona), Discrete
Mathematics 273 (2003), 235-260.
(pdf)
Abstract
- J. Diaz, N. Do, M. Serna, and N.C. Wormald.
Bounds on the max and min bisection of random cubic and random 4-regular graphs.
Theoretical Computer Science 2483 (2003) 531-547.
(pdf)
Abstract
- S. Bau, N.C. Wormald and S.M. Zhou, Decycling numbers of
random regular graphs, Random Structures and Algorithms
21 (2002), 397-413. (pdf)
Abstract
- J. Diaz, N. Do, M. Serna, and N.C. Wormald. Bounds
on the max and min bisection of random cubic and random 4-regular graphs.
In J. Rolim and S. Vadhan, eds, Randomization and Approximation
Techniques in Computer Science, Lecture Notes in Computer Science
2483, pp. 114-125, Springer, 2002.
(See journal version above.)
- W. Duckworth, N.C. Wormald and M. Zito, Maximum
induced matchings of random cubic graphs, Journal of Computational
and Applied Mathematics 142 (2002), 39-50.
(pdf)Abstract
[Earlier version: Sixth Annual International Computing and Combinatorics
Conference (COCOON 2000) (ps.gz)
Abstract]
- W. Duckworth and N.C. Wormald, Minimum independent
dominating sets of random cubic graphs, Random Structures and Algorithms
21 (2002),
147-161. (pdf )
Abstract
- C.S. Greenhill, S. Janson, J. H. Kim, and N.C. Wormald, Permutation
graphs and contiguity, Combinatorics, Probability and Computing
11 (2002), 273-298. (pdf of preprint) Abstract
- 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
- 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
- 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
- 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
- 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
-
A. Frieze, M. Jerrum, M. Molloy, R.W. Robinson and N.C. Wormald,
Generating and counting Hamilton cycles in random regular graphs,
Journal of Algorithms
21 (1996), 176-198.
(pdf)
Abstract
-
R.W. Robinson and N.C. Wormald,
Almost all regular graphs are hamiltonian,
Random Structures and Algorithms
5 (1994), 363-374.
(pdf)
Abstract
BACK to top
Random Graph Processes
- H. Acan, A. Collevecchio and Abbas Mehrabian and N. Wormald,
On the push&pull protocol for rumour spreading,
SIAM J. Discrete Math.
31 (2017), 647-668.
- H. Acan, A. Collevecchio and Abbas Mehrabian and N. Wormald,
On the push&pull protocol for rumour spreading,
In Proceedings of the 2015 ACM Symposium on Principles of
Distributed Computing (2015), 405-412. (extended abstract)
- S. Gerke, A. Steger and N. Wormald,
Pegging graphs yields a small diameter,
Combinatorics, Probability and Computing
20 (2011), 239-248.
- P. Gao and N. Wormald,
Rate of convergence of the short cycle distribution in random regular graphs generated by pegging,
Electronic Journal of Combinatorics
16 (2009), RP 44, 19 pp.
(pdf)
Abstract
- P. Gao and N. Wormald,
Short cycles distribution in random regular graphs produced by pegging,
Random Structures and Algorithms
34 (2009), 54-86.
(pdf)
Abstract
- J. Diaz, X. Perez, M. Serna and N.C. Wormald,
Walkers on the cycle and the grid,
SIAM J. Discrete Math.
22 (2008), 747-775.
(pdf)
Abstract
- J. Spencer and N. Wormald, Birth control for giants,
Combinatorica
27 (2007), 587-628.
(pdf)
Abstract
- A. Telcs, N. Wormald and S. Zhou, Hamiltonicity of random graphs produced by 2-processes, Random Structures and Algorithms
31 (2007), 450-481.
(pdf)
Abstract
- J. Diaz, X. Perez, M. Serna and N.C. Wormald, Connectivity for wireless agents moving on a cycle or grid, Lecture Notes in Computer Science, 3404 STACS 2005 pp. 353-364. Springer, Berlin, 2005. (pdf)
Abstract
- C.S. Greenhill, A. Rucinski, and N.C. Wormald, Random hypergraph
processes with degree restrictions, Graphs and Combinatorics
20, (2004), 319-332.
(pdf)
Abstract
- T. Bohman, A. Frieze, and N.C. Wormald, Avoidance of a giant component in half the edge set of a random graph, Random Structures and Algorithms 25 (2004), 432-449. (pdf)
Abstract
- C.S. Greenhill, A. Rucinski and N.C. Wormald Connectivity
of the random star process, Combinatorics, Probability and Computing
12 (2003), 269-283. (pdf)
Abstract
- A. Rucinski and N.C. Wormald, Connectedness of graphs generated
by a random d-process, J. Austral. Math. Soc.
72 (2002), 67-85. (ps.gz of preprint)
Abstract
- H.D. Robalewska and N.C. Wormald, Random star processes,
Combinatorics, Probability and Computing 9 (2000), 33-43.
Abstract
- 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. pdf of preprint (A list of corrections and addenda may be found here. ) Abstract
- A. Rucinski and N.C. Wormald, Random graph processes with
maximum degree 2, Annals of Applied Probability 7 (1997), 183-199.
Abstract
-
N.C. Wormald,
Differential equations for random processes and random graphs,
Annals of Applied Probability
5 (1995), 1217-1235.
BACK to top
Web-graphs, Evolving Networks and Social Networks
- A. Mehrabian and N. Wormald,
It's a small world for random surfers,
Algorithmica
76 (2016), 344-380.
- A. Collevecchio, Abbas Mehrabian and N. Wormald,
Longest paths in random Apollonian networks
and largest r-ary subtrees of random d-ary recursive trees,
Journal of Applied Probability
53 (2016), 846-856.
- A. Mehrabian and N. Wormald,
It's a small world for random surfers,
In Approximation, randomization, and combinatorial optimization 2014
(2014), 857-871 (extended abstract version).
- E. Ebrahimzadeh, L. Farczadi, P. Gao, A. Mehrabian, C.M. Sato, N.
Wormald and J. Zung,
On the Longest Paths and the Diameter in Random Apollonian
Networks,
Random Structures and Algorithms
45 (2014), 703-725.
- W. Richards and N. Wormald,
The Evolution and Structure of Social Networks,
Network Science
2 (2014), 326-340.
- E. Ebrahimzadeh, L. Farczadi, P. Gao, A. Mehrabian, C.M. Sato, N.
Wormald and J. Zung,
On the Longest Paths and the Diameter in Random Apollonian
Networks, manuscript (extended abstract version).
- S. Gerke, A. Steger and N. Wormald,
Pegging graphs yields a small diameter,
Combinatorics, Probability and Computing
20 (2011), 239-248.
- P. Gao and N. Wormald,
Rate of convergence of the short cycle distribution in random regular graphs generated by pegging,
Electronic Journal of Combinatorics
16 (2009), RP 44, 19 pp.
(pdf)
Abstract
- P. Gao and N. Wormald,
Short cycles distribution in random regular graphs produced by pegging,
Random Structures and Algorithms
34 (2009), 54-86.
(pdf)
Abstract
- W. Richards and N. Wormald,
Representing small group evolution,
Proceedings - 12th IEEE International Conference on Computational Science and Engineering, CSE 2009 (SocialCom 2009, Vancouver, August 2009)
4 (2009), 159-165.
(pdf)
Abstract
- P. Pralat and N.C. Wormald, Growing protean graphs, Internet Mathematics
4 (2009), 1-16.
(pdf)
Abstract
BACK to top
Random Maps
- Z. Gao and N.C. Wormald,
Asymptotic normality determined by high moments, and submap counts of random maps,
Probability Theory and Related Fields
130 (2004), 368-376.
(pdf)
Abstract
- Z. Gao and N.C. Wormald, Sharp concentration of the number of
submaps in random planar triangulations, Combinatorica
23 (2003), 467-486. (pdf) Abstract
- 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
- 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
-
E.A. Bender, Z. Gao, L.B. Richmond and N.C. Wormald,
Asymptotic properties of rooted 3-connected maps on surfaces,
J. Austral. Math. Soc. (Series A)
60 (1996), 31-41.
-
E.A. Bender, L.B. Richmond and N.C. Wormald,
Largest 4-connected components of 3-connected planar triangulations,
Random Structures and Algorithms
7 (1995), 273-285.
-
L.B. Richmond and N.C. Wormald,
Almost all maps are asymmetric,
J. Combinatorial Theory (Series B)
63 (1995), 1-7.
BACK to top
Asymptotic Enumeration
- P. Gao and N. Wormald,
Enumeration of graphs with a heavy-tailed degree sequence,
Advances in Mathematics
287 (2016), 412-450.
- X. Perez-Gimenez and N. Wormald,
Asymptotic enumeration of strongly connected digraphs by vertices and edges,
Random Structures and Algorithms
43 (2013), 80-114.
(pdf)
Abstract
- G.Kemkes, C.M. Sato and N. Wormald,
Asymptotic enumeration of sparse 2-connected graphs,
Random Structures and Algorithms
43 (2013), 354-376.
(pdf)
Abstract
- E.A. Bender, A. B. Olde Daalhuis, Z. Gao, L.B. Richmond and N.C. Wormald,
Asymptotics of some convolutional recurrences,
Electronic Journal of Combinatorics
17 (2010), Research Paper 1, 11pp.
(pdf)
Abstract
- B. Pittel and N.C. Wormald,
Asymptotic enumeration of sparse
graphs with a minimum degree constraint,
J. Combinatorial Theory, Series A
101 (2003), 249-263.
(pdf)
- E.A. Bender, Z. Gao and N.C. Wormald, The number of labeled
2-connected planar graphs, Electronic Journal of Combinatorics
9 (2002), Research Paper 43, 13 pp. (pdf) (A correction may be found
here. ) Abstract
- 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 11 (2002), 373-392. (ps.gz)
Description
- 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
- D. Stark and N.C. Wormald, The asymptotic number of d-dimensional
convex polygons, J. Combinatorial Theory, Series A 80 (1997), 196-217.
Abstract
BACK to top
Enumeration
- Z. Gao, V.A. Liskovets and N.C. Wormald,
Enumeration of unrooted odd-valent regular planar maps,
Annals of Combinatorics
13 (2009), 233-259.
(pdf)
Abstract
- N.C. Wormald, Tournaments with many Hamilton cycles,
preprint.
(pdf)
Abstract
-
R. Castelo and N.C. Wormald, Enumeration
of P_4-free chordal graphs, Graphs and Combinatorics
19 (2003), 467-474. (pdf)
Abstract
- Z. Gao and N.C. Wormald, Enumeration of rooted cubic
planar maps, Annals of Combinatorics 6 (2002), 313-325. (ps.gz)
Abstract
- Z. Gao, I.M. Wanless and N.C. Wormald, Counting 5-connected
planar triangulations, J. Graph Theory 38 (2001), 18-35.
Abstract
BACK to top
Graph Theory
- C. Hoppen and N. Wormald,
Local algorithms, regular graphs of large girth, and random regular graphs,
J. Combinatorial Theory, Series B
121 (2016), 367-397.
- N. Alon and N. Wormald,
High degree graphs contain large-star factors,
in "Fete of Combinatorics", Gy. Katona, A. Schrijver and T. Szonyi, eds, Springer,
Bolyai Soc. Math. Studies
20 (2010), 9-21.
(pdf)
Abstract
- W. Duckworth and N.C. Wormald, Linear programming and the worst-case analysis of greedy algorithms
on cubic graphs,
Electronic Journal of Combinatorics
17 (2010), Research Paper 177, 29 pp.
(pdf)
Abstract
- C. Hoppen and N. Wormald,
Induced forests in regular graphs with large girth,
Combinatorics, Probability and Computing
17 (2008), 389-410.
(pdf)
Abstract
- J. Lauer and N.C. Wormald, Large independent sets in regular graphs of large girth,
J. Combinatorial Theory, Series B
97 (2007), 999-1009.
(pdf)
Abstract
- 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
- 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
- H. Assiyatun and N.C. Wormald, Covering regular graphs with
forests of small trees, Australasian Journal of Combinatorics
22 (2000), 219-226. Abstract
- R.E.L. Aldred and N.C. Wormald, Linear k-arboricity of regular
graphs, Australasian Journal of Combinatorics 18 (1998), 97-104.
Abstract
- T. Lindquester and N.C. Wormald, Factorisation of regular
graphs into forests of paths, Discrete Mathematics 186 (1998) 217-226.
Abstract
-
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
-
B. Jackson and N.C. Wormald,
On the linear {$k$}-arboricity of cubic graphs,
Discrete Mathematics
162 (1996), 293-297.
-
B. Jackson and N.C. Wormald,
Long cycles and 3-connected spanning subgraphs of bounded degree in 3-connected K_{1,d}-free graphs,
J. Combinatorial Theory (Series B)
63 (1995), 163-169.
-
Z. Gao and N.C. Wormald,
Spanning Eulerian subgraphs of bounded degree in triangulations,
Graphs and Combinatorics
10 (1994), 121-131.
-
P.J. Cameron, C.E. Praeger and N.C. Wormald,
Infinite highly arc transitive digraphs and universal covering digraphs,
Combinatorica
14 (1993), 377-396.
BACK to top
Probability Theory
- Z. Gao and N.C. Wormald,
Asymptotic normality determined by high moments, and submap counts of random maps,
Probability Theory and Related Fields 130 (2004), 368-376.
(pdf)
Abstract
- A. Telcs and N.C. Wormald, Branching and tree indexed random
walks on fractals, J. Applied Probab. 36 (1999), 999-1011.
Abstract
BACK to top
Algorithms
- P. Gao and N. Wormald.
Uniform generation of random regular graphs,
SIAM J. Computing
46 (2017) 1395--1427.
- H. Acan, A. Collevecchio and Abbas Mehrabian and N. Wormald,
On the push&pull protocol for rumour spreading,
SIAM J. Discrete Math.
31 (2017), 647-668.
- C. Hoppen and N. Wormald,
Local algorithms, regular graphs of large girth, and random regular graphs,
J. Combinatorial Theory, Series B
121 (2016), 367-397.
- H. Acan, A. Collevecchio and Abbas Mehrabian and N. Wormald,
On the push&pull protocol for rumour spreading,
In Proceedings of the 2015 ACM Symposium on Principles of
Distributed Computing (2015), 405-412. (extended abstract)
-
P. Gao and N. Wormald,
Uniform generation of random regular graphs,
In Proceedings of 2015 IEEE 56th Annual Symposium on Foundations
of Computer Science (FOCS)
(2015), 1218--1230.
-
P. Gao and N. Wormald,
Orientability thresholds for random hypergraphs,
Combinatorics, Probability and Computing
24 (2015), 774-824.
(pdf)
Abstract
- P. Gao and N. Wormald,
Load balancing and orientability thresholds for random hypergraphs,
Proceedings of STOC (ACM)
(2010), 97-104. (The journal version of this paper is "Orientability thresholds for random hypergraphs", listed above.)
(pdf)
Abstract
- E. Mossel, D. Weitz and N. Wormald,
On the hardness of sampling independent sets beyond the tree threshold,
Probability Theory and Related Fields
143 (2009), 401-439.
(pdf)
Abstract
- J. Cain, P. Sanders and N. Wormald, The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation,
Proceedings of 18th Annual ACM-SIAM SODA 469-476 (2007).
(pdf)
Abstract
- N.C. Wormald Analysis of greedy algorithms
on graphs with bounded degrees, EuroComb '01 (Barcelona), Discrete
Mathematics 273 (2003), 235-260.
(pdf)
Abstract
- 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 1 (2003), 67-76.
(pdf ) Abstract
- 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
- 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., pp. 63-75. Curtin University, Perth, (1999).
(ps.gz of preprint) Abstract
- A. Steger and N.C. Wormald, Generating random regular graphs
quickly. Combinatorics, Probab. and Comput. 8 (1999), 377-396.
Abstract
- W.D. Smith and N.C. Wormald, Geometric separator theorems
and applications. (Draft manuscript, 50 pages. pdf) Abstract
- 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.)
- A. Moffat, O. Petersson and N.C. Wormald, A tree-based mergesort,
Acta Informatica 35 (1998), 775-793. Abstract
-
B.S. Majewski, N.C. Wormald, G. Havas and Z.J. Czech,
A family of perfect hashing methods,
Computer Journal
39 (1996), 547-554.
-
G. Havas, B.S. Majewski, N.C. Wormald and Z.J. Czech,
Graphs, hypergraphs and hashing,
Springer Lecture Notes in Computer Science
790 (1994), 153-165.
-
P. Eades and N.C. Wormald,
Edge crossings in drawings of bipartite graphs,
Algorithmica
11 (1994), 379-403.
BACK to top
Evolutionary Trees
- 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
-
M.P. Ng and N.C. Wormald,
Reconstruction of rooted trees from subtrees,
Discrete Applied Mathematics
69 (1996), 19-31.
BACK to top
Minimum Steiner Trees
- M. Brazil, J.H. Rubinstein, D.A. Thomas, J.F. Weng and N. Wormald,
Gradient-constrained minimum networks, III. Fixed topology,
Journal of Optimization Theory and Applications
155 (2012), 336-354.
- J.H. Rubinstein, J. Weng and N. Wormald, Approximations and Lower Bounds for the Length of Minimal
Euclidean Steiner Trees ,
J. Global Optimization 35 (2006), 573-592.
(pdf)
Abstract
- 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
-
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
- 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
- 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
- M. Brazil, T. Cole, J.H. Rubinstein, D.A. Thomas, J.F. Weng and N.C. Wormald,
Minimal Steiner trees for $2^k \times 2^k$ checkerboards,
J. Combinatorial Theory, Series A
73 (1996), 91-110.
BACK to top
Underground Mine Optimisation
- M. Brazil, P.A. Grossman, D.H. Lee, J.H. Rubinstein, D.A. Thomas and N.C. Wormald,
Access Optimisation Tools in Underground Mine Design,
In ''International Symposium. Orebody Modelling and Strategic Mine Planning: Old and New Dimensions in a Changing World.'' Proceedings of the Orebody Modelling and Strategic Mine Planning Conference
16-17 March 2009,
Australasian Institute of Mining and Metallurgy (2009), 237-241.
(pdf of preprint) Abstract
- M. Brazil, P.A. Grossman, D.H. Lee, J.H. Rubinstein, D.A. Thomas and N.C. Wormald,
Decline design in underground mines using constrained path optimisation,
Mining Technology: IMM Transactions Section A
117 (2008), 93-99.
(pdf of preprint) Abstract
- M. Brazil, P.A. Grossman, D.H. Lee, J.H. Rubinstein, D.A. Thomas and N.C. Wormald,
Constrained path optimisation for underground mine layout,
The 2007 International
Conference of Applied and Engineering Mathematics (ICAEM 07), London
(2007), 856-861. (Conference version of ``Decline design in underground mines using constrained path optimisation'' listed above.)
(pdf of preprint) Abstract
- D.A. Thomas, M. Brazil, D. Lee and N.C.
Wormald,
Network modelling of underground mine layout: Two case studies,
International Transactions in Operational Research
14 (2007), 143-158.
(pdf of preprint) Abstract
- M. Brazil, D. Lee , J.H. Rubinstein, D.A. Thomas, J.F. Weng and N.C.
Wormald,
Optimisation in the design of underground mine access,
In "Orebody Modelling and Strategic Mine Planning" Spectrum Series 14 (R. Dimitrakopoulos, ed.), pp. 121-124. AusIMM (2005).
(pdf of preprint) Abstract
- M. Brazil, D.H. Lee, M. Van Leuven, J.H. Rubinstein, D.A. Thomas and N.C. Wormald,
Optimising declines in underground mines, Mining Technology
112 (2003), 164-170.
Abstract
- 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, Trans. South African Inst. of Electrical Engineers
93 (2002), 97-103.
(pdf)
- 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
- 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
BACK to top
Chronological list of recent papers published
2017
- P. Gao and N. Wormald.
Uniform generation of random regular graphs,
SIAM J. Computing
46 (2017) 1395-1427.
- L. Kang and N. Wormald,
Minimum power dominating sets of random cubic graphs,
J. Graph Theory
85 (2017) 152-171.
- H. Acan, A. Collevecchio and Abbas Mehrabian and N. Wormald,
On the push&pull protocol for rumour spreading,
SIAM J. Discrete Math.
31 (2017), 647-668.
- E. Lubetzky, J. Kahn and N. Wormald,
Cycle factors and renewal theory, preprint.
Communications in Pure and Applied Mathematics
70 (2017) 289-339.
2016
- E. Lubetzky, J. Kahn and N. Wormald,
The threshold for combs in random graphs,
Random Structures and Algorithms
48 (2016), 794-802.
- A. Mehrabian and N. Wormald,
It's a small world for random surfers,
Algorithmica
76 (2016), 344-380.
- A. Collevecchio, Abbas Mehrabian and N. Wormald,
Longest paths in random Apollonian networks
and largest r-ary subtrees of random d-ary recursive trees,
Journal of Applied Probability
53 (2016), 846-856.
- C. Hoppen and N. Wormald,
Local algorithms, regular graphs of large girth, and random regular graphs,
J. Combinatorial Theory, Series B
121 (2016), 367-397.
- P. Gao and N. Wormald,
Enumeration of graphs with a heavy-tailed degree sequence,
Advances in Mathematics
287 (2016), 412-450.
- P. Pralat and N. Wormald,
Meyniel's conjecture holds for random graphs,
Random Structures and Algorithms
48 (2016), 396-421.
2015
- H. Acan, A. Collevecchio and Abbas Mehrabian and N. Wormald,
On the push&pull protocol for rumour spreading,
In Proceedings of the 2015 ACM Symposium on Principles of
Distributed Computing (2015), 405-412. (extended abstract)
-
P. Gao and N. Wormald,
Uniform generation of random regular graphs,
In Proceedings of 2015 IEEE 56th Annual Symposium on Foundations
of Computer Science (FOCS)
(2015), 1218--1230.
-
P. Gao and N. Wormald,
Orientability thresholds for random hypergraphs,
Combinatorics, Probability and Computing
24 (2015), 774-824.
(pdf)
Abstract
2014
- A. Mehrabian and N. Wormald,
It's a small world for random surfers,
In Approximation, randomization, and combinatorial optimization 2014
(2014), 857-871 (extended abstract version).
- E. Ebrahimzadeh, L. Farczadi, P. Gao, A. Mehrabian, C.M. Sato, N.
Wormald and J. Zung,
On the Longest Paths and the Diameter in Random Apollonian
Networks,
Random Structures and Algorithms
45 (2014), 703-725.
- W. Richards and N. Wormald,
The Evolution and Structure of Social Networks,
Network Science
2 (2014), 326-340.
- I. Benjamini, G. Kozma and N. Wormald,
The mixing time of the giant component of a random graph,
Random Structures and Algorithms
45 (2014), 383-407.
- B. Kolesnik and N. Wormald,
Lower bounds for the isoperimetric numbers of random regular graphs,
SIAM J. Discrete Math.
428 (2014), 553-575.
2013
- E. Ebrahimzadeh, L. Farczadi, P. Gao, A. Mehrabian, C.M. Sato, N.
Wormald and J. Zung,
On the Longest Paths and the Diameter in Random Apollonian
Networks,
Electronic Notes in Discrete Mathematics
43 (2013), 355-365.
(extended abstract version)
- X. Perez-Gimenez and N. Wormald,
Asymptotic enumeration of strongly connected digraphs by vertices and edges,
Random Structures and Algorithms
43 (2013), 80-114.
(pdf)
Abstract
- G.Kemkes, C.M. Sato and N. Wormald,
Asymptotic enumeration of sparse 2-connected graphs,
Random Structures and Algorithms
43 (2013), 354-376.
(pdf)
Abstract
- A. Mehrabian and N. Wormald,
On the Stretch Factor of Randomly Embedded Random Graphs,
Discrete and Computational Geometry
49 (2013), 647-658.
- G. Kemkes and N. Wormald,
An improved upper bound on the length of the longest cycle of a post-critical random graph,
SIAM J. Discrete Math.
27 (2013), 342-362.
(pdf)
Abstract
2012
- P. Gao, Y. Su and N. Wormald,
Induced subgraphs in sparse random graphs with given degree sequence,
European Journal of Combinatorics
33 (2012), 1142-1166.
(pdf)
Abstract
- F.C. Botelho, N. Wormald and N. Ziviani,
Cores of Random r-Partite Hypergraphs,
Information Processing Letters
112 (2012), 314-319.
- M. Brazil, J.H. Rubinstein, D.A. Thomas, J.F. Weng and N. Wormald,
Gradient-constrained minimum networks, III. Fixed topology,
Journal of Optimization Theory and Applications
155 (2012), 336-354.
2011
- T. Muller and X. Perez-Gimenez and N. Wormald,
Disjoint Hamilton cycles in the random geometric graph,
J. Graph Theory
68 (2011), 299-322.
- S. Gerke, A. Steger and N. Wormald,
Pegging graphs yields a small diameter,
Combinatorics, Probability and Computing
20 (2011), 239-248.
- M. Krivelevich, B. Sudakov and N. Wormald,
Regular induced subgraphs of a random graph,
Random Structures and Algorithms
38 (2011), 235-250.
- I. Benjamini, C. Hoppen, E. Ofek, P. Pralat and N. Wormald,
Geodesics and almost geodesic cycles in random regular graphs,
J. Graph Theory
66 (2011), 115-136.
- P. Pralat, J. Verstraete and N. Wormald,
On the threshold for k-regular subgraphs of random graphs,
Combinatorica.
31 (2011), 565-581.
(pdf)
Abstract
2010
- N. Alon and N. Wormald,
High degree graphs contain large-star factors,
in "Fete of Combinatorics", Gy. Katona, A. Schrijver and T. Szonyi, eds, Springer,
Bolyai Soc. Math. Studies
20 (2010), 9-21.
(pdf)
Abstract
- G. Kemkes, X. Perez-Gimenez and N. Wormald,
On the chromatic number of random d-regular graphs,
Advances in Mathematics
223 (2010), 300-328.
(pdf)
Abstract
-
O. Riordan and N. Wormald,
The diameter of sparse random graphs,
Combinatorics, Probability and Computing
19 (2010), 835-926.
(pdf)
Abstract
- W. Duckworth and N.C. Wormald, Linear programming and the worst-case analysis of greedy algorithms
on cubic graphs,
Electronic Journal of Combinatorics
17 (2010), Research Paper 177, 29 pp.
(pdf)
Abstract
- P. Gao and N. Wormald,
Load balancing and orientability thresholds for random hypergraphs,
Proceedings of STOC (ACM)
(2010), 97-104. (The journal version of this paper is "Orientability thresholds for random hypergraphs", listed above.)
(pdf)
Abstract
- E.A. Bender, A. B. Olde Daalhuis, Z. Gao, L.B. Richmond and N.C. Wormald,
Asymptotics of some convolutional recurrences,
Electronic Journal of Combinatorics
17 (2010), Research Paper 1, 11pp.
(pdf)
Abstract
2009
- E. Mossel, D. Weitz and N. Wormald,
On the hardness of sampling independent sets beyond the tree threshold,
Probability Theory and Related Fields
143 (2009), 401-439.
(pdf)
Abstract
- Z. Gao, V.A. Liskovets and N.C. Wormald,
Enumeration of unrooted odd-valent regular planar maps,
Annals of Combinatorics
13 (2009), 233-259.
(pdf)
Abstract
- J. Diaz, A.C. Kaporis, G.D. Kemkes, L.M. Kirousis, X. Perez and N. Wormald,
On the chromatic number of random 5-regular graphs,
J. Graph Theory
61 (2009), 157-191.
(pdf)
Abstract
- P. Gao and N. Wormald,
Rate of convergence of the short cycle distribution in random regular graphs generated by pegging,
Electronic Journal of Combinatorics
16 (2009), RP 44, 19 pp.
(pdf)
Abstract
- P. Gao and N. Wormald,
Short cycles distribution in random regular graphs produced by pegging,
Random Structures and Algorithms
34 (2009), 54-86.
(pdf)
Abstract
- W. Richards and N. Wormald,
Representing small group evolution,
Proceedings - 12th IEEE International Conference on Computational Science and Engineering, CSE 2009 (SocialCom 2009, Vancouver, August 2009)
4 (2009), 159-165.
(pdf)
Abstract
- P. Pralat and N.C. Wormald, Growing protean graphs, Internet Mathematics
4 (2009), 1-16.
(pdf)
Abstract
- M. Brazil, P.A. Grossman, D.H. Lee, J.H. Rubinstein, D.A. Thomas and N.C. Wormald,
Access Optimisation Tools in Underground Mine Design,
In ''International Symposium. Orebody Modelling and Strategic Mine Planning: Old and New Dimensions in a Changing World.'' Proceedings of the Orebody Modelling and Strategic Mine Planning Conference
16-17 March 2009,
Australasian Institute of Mining and Metallurgy (2009), 237-241.
(pdf of preprint) Abstract
2008
- C. Hoppen and N. Wormald,
Induced forests in regular graphs with large girth,
Combinatorics, Probability and Computing
17 (2008), 389-410.
(pdf)
Abstract
- J. Diaz, X. Perez, M. Serna and N.C. Wormald,
Walkers on the cycle and the grid,
SIAM J. Discrete Math.
22 (2008), 747-775.
(pdf)
Abstract
- N. Alon , P. Pralat and N. Wormald,
Cleaning d-regular graphs with brushes,
SIAM J. Discrete Math.
23 (2008), 233-250.
(pdf)
Abstract
- C.S. Greenhill, F.B. Holt and N. Wormald,
Expansion properties of a random regular graph after random vertex deletions,
Europ. J. Combin.
29 (2008), 1139-1150.
(pdf)
Abstract
- Z. Gao and N. Wormald,
Distribution of subgraphs of random regular graphs,
Random Structures and Algorithms
32 (2008), 38-48.
(pdf)
Abstract
-
N.C. Wormald and S. Zhou,
Large forbidden trade volumes of random graphs,
Discrete Mathematics
308 (2008), 2751-2755.
(pdf)
Abstract
- M. Brazil, P.A. Grossman, D.H. Lee, J.H. Rubinstein, D.A. Thomas and N.C. Wormald,
Decline design in underground mines using constrained path optimisation,
Mining Technology: IMM Transactions Section A
117 (2008), 93-99.
(pdf of preprint) Abstract
2007
- J. Lauer and N.C. Wormald, Large independent sets in regular graphs of large girth,
J. Combinatorial Theory, Series B
97 (2007), 999-1009.
(pdf)
Abstract
- J. Cain, P. Sanders and N. Wormald, The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation,
Proceedings of 18th Annual ACM-SIAM SODA 469-476 (2007).
(pdf)
Abstract
- M.-E. Messinger, R.J. Nowakowski, P. Pralat and N. Wormald,
Cleaning random d-regular graphs with brushes using a degree-greedy algorithm,
in CAAN 2007, Lecture Notes in Computer Science
4852 (2007), 13-26.
(pdf)
Abstract
- S. Janson and N. Wormald,
Rainbow Hamilton cycles in random regular graphs,
Random Structures and Algorithms
30 (2007), 35-49.
(pdf)
Abstract
- J. Diaz, M. Serna, and N.C. Wormald, Computation of the bisection
width for random d-regular graphs,
Theoretical Computer Science
382 (2007), 120-130.
(pdf)
Abstract
- L. Shi and N. Wormald, Colouring random regular graphs,
Combinatorics, Probability and Computing
16 (2007), 459-494.
(pdf)
Abstract
- L. Shi and N. Wormald, Colouring random 4-regular graphs, Combinatorics, Probability and Computing
16 (2007), 309-344.
(pdf)
Abstract
- J. Spencer and N. Wormald, Birth control for giants,
Combinatorica
27 (2007), 587-628.
(pdf)
Abstract
- A. Telcs, N. Wormald and S. Zhou, Hamiltonicity of random graphs produced by 2-processes, Random Structures and Algorithms
31 (2007), 450-481.
(pdf)
Abstract
- M. Brazil, P.A. Grossman, D.H. Lee, J.H. Rubinstein, D.A. Thomas and N.C. Wormald,
Constrained path optimisation for underground mine layout,
The 2007 International
Conference of Applied and Engineering Mathematics (ICAEM 07), London
(2007), 856-861. (Conference version of ``Decline design in underground mines using constrained path optimisation'' listed above.)
(pdf of preprint) Abstract
- D.A. Thomas, M. Brazil, D. Lee and N.C.
Wormald,
Network modelling of underground mine layout: Two case studies,
International Transactions in Operational Research
14 (2007), 143-158.
(pdf of preprint) Abstract
BACK to top