Nicholas C. Wormald

Affiliations:
  • Monash University, Department of Mathematical Sciences
  • University of Waterloo, Department of Mathematics, Canada


According to our database1, Nicholas C. Wormald authored at least 186 papers between 1977 and 2023.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of one.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Asymptotic enumeration of digraphs and bipartite graphs by degree sequence.
Random Struct. Algorithms, March, 2023

2022
Component Games on Random Graphs.
Comb., December, 2022

Semi-labeled unrooted binary tree optimization subject to nonnegativity.
Networks, 2022

Engineering Uniform Sampling of Graphs with a Prescribed Power-law Degree Sequence.
Proceedings of the Symposium on Algorithm Engineering and Experiments, 2022

2021
Fast uniform generation of random graphs with given degree sequences.
Random Struct. Algorithms, 2021

Full rainbow matchings in graphs and hypergraphs.
Comb. Probab. Comput., 2021

Linear-time uniform generation of random sparse contingency tables with specified marginals.
CoRR, 2021

2020
The height of depth-weighted random recursive trees.
Random Struct. Algorithms, 2020

Almost all 5-regular graphs have a 3-flow.
J. Graph Theory, 2020

Optimal Tree of a Complete Weighted Graph.
Proceedings of the Recent Advances in Computational Optimization, 2020

On Finding the Optimal Tree of a Complete Weighted Graph.
Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, 2020

2019
Meyniel's conjecture holds for random d-regular graphs.
Random Struct. Algorithms, 2019

A Limit Theorem for the Six-length of Random Functional Graphs with a Fixed Degree Sequence.
Electron. J. Comb., 2019

2018
The Probability of Non-Existence of a Subgraph in a Moderately Sparse Random Graph.
Comb. Probab. Comput., 2018

The Number of Satisfying Assignments of Random Regular k-SAT Formulas.
Comb. Probab. Comput., 2018

Local Algorithms, Regular Graphs of Large Girth, and Random Regular Graphs.
Comb., 2018

Uniform generation of random graphs with power-law degree sequences.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017
On the Push&Pull Protocol for Rumor Spreading.
SIAM J. Discret. Math., 2017

Uniform Generation of Random Regular Graphs.
SIAM J. Comput., 2017

Minimum Power Dominating Sets of Random Cubic Graphs.
J. Graph Theory, 2017

2016
Meyniel's conjecture holds for random graphs.
Random Struct. Algorithms, 2016

The threshold for combs in random graphs.
Random Struct. Algorithms, 2016

Properties of regular graphs with large girth via local algorithms.
J. Comb. Theory B, 2016

Longest paths in random Apollonian networks and largest r-ary subtrees of random d-ary recursive trees.
J. Appl. Probab., 2016

It's a Small World for Random Surfers.
Algorithmica, 2016

2015
Orientability Thresholds for Random Hypergraphs.
Comb. Probab. Comput., 2015

On the Push&Pull Protocol for Rumour Spreading: [Extended Abstract].
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

2014
Lower Bounds for the Isoperimetric Numbers of Random Regular Graphs.
SIAM J. Discret. Math., 2014

On longest paths and diameter in random apollonian network.
Random Struct. Algorithms, 2014

The mixing time of the giant component of a random graph.
Random Struct. Algorithms, 2014

The evolution and structure of social networks.
Netw. Sci., 2014

On the push&pull protocol for rumour spreading.
CoRR, 2014

2013
An Improved Upper Bound on the Length of the Longest Cycle of a Supercritical Random Graph.
SIAM J. Discret. Math., 2013

Asymptotic enumeration of strongly connected digraphs by vertices and edges.
Random Struct. Algorithms, 2013

Asymptotic enumeration of sparse 2-connected graphs.
Random Struct. Algorithms, 2013

On the Longest Paths and the Diameter in Random Apollonian Networks.
Electron. Notes Discret. Math., 2013

On the Stretch Factor of Randomly Embedded Random Graphs.
Discret. Comput. Geom., 2013

2012
Gradient-Constrained Minimum Networks. III. Fixed Topology.
J. Optim. Theory Appl., 2012

Cores of random r-partite hypergraphs.
Inf. Process. Lett., 2012

Induced subgraphs in sparse random graphs with given degree sequences.
Eur. J. Comb., 2012

2011
Regular induced subgraphs of a random Graph.
Random Struct. Algorithms, 2011

Disjoint Hamilton cycles in the random geometric graph.
J. Graph Theory, 2011

Geodesics and almost geodesic cycles in random regular graphs.
J. Graph Theory, 2011

Pegging Graphs Yields a Small Diameter.
Comb. Probab. Comput., 2011

On the threshold for k-regular subgraphs of random graphs.
Comb., 2011

2010
The Diameter of Sparse Random Graphs.
Comb. Probab. Comput., 2010

Linear Programming and the Worst-Case Analysis of Greedy Algorithms on Cubic Graphs.
Electron. J. Comb., 2010

Asymptotics of Some Convolutional Recurrences.
Electron. J. Comb., 2010

Load balancing and orientability thresholds for random hypergraphs.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

2009
Short cycle distribution in random regular graphs recursively generated by pegging.
Random Struct. Algorithms, 2009

On the chromatic number of a random 5-regular graph.
J. Graph Theory, 2009

Rate of Convergence of the Short Cycle Distribution in Random Regular Graphs Generated by Pegging.
Electron. J. Comb., 2009

Representing Small Group Evolution.
Proceedings of the 12th IEEE International Conference on Computational Science and Engineering, 2009

2008
Walkers on the Cycle and the Grid.
SIAM J. Discret. Math., 2008

Cleaning Regular Graphs with Brushes.
SIAM J. Discret. Math., 2008

Distribution of subgraphs of random regular graphs.
Random Struct. Algorithms, 2008

Corrigendum to "Counting connected graphs inside-out" [J. Combin. Theory Ser. B 93 (2005) 127-172].
J. Comb. Theory B, 2008

Expansion properties of a random regular graph after random vertex deletions.
Eur. J. Comb., 2008

Large forbidden trade volumes and edge packings of random graphs.
Discret. Math., 2008

Induced Forests in Regular Graphs with Large Girth.
Comb. Probab. Comput., 2008

2007
Bounds on the bisection width for random d -regular graphs.
Theor. Comput. Sci., 2007

Hamiltonicity of random graphs produced by 2-processes.
Random Struct. Algorithms, 2007

Rainbow Hamilton cycles in random regular graphs.
Random Struct. Algorithms, 2007

Large independent sets in regular graphs of large girth.
J. Comb. Theory B, 2007

Network modelling of underground mine layout: two case studies.
Int. Trans. Oper. Res., 2007

Growing Protean Graphs.
Internet Math., 2007

Colouring Random Regular Graphs.
Comb. Probab. Comput., 2007

Colouring Random 4-Regular Graphs.
Comb. Probab. Comput., 2007

Birth control for giants.
Comb., 2007

Constrained Path Optimisation for Underground Mine Layout.
Proceedings of the World Congress on Engineering, 2007

The random graph threshold for <i>k</i>-orientiability and a fast algorithm for optimal multiple-choice allocation.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Cleaning Random <i>d</i>-Regular Graphs with Brushes Using a Degree-Greedy Algorithm.
Proceedings of the Combinatorial and Algorithmic Aspects of Networking, 4th Workshop, 2007

2006
The generalized acyclic edge chromatic number of random regular graphs.
J. Graph Theory, 2006

Approximations and Lower Bounds for the Length of Minimal Euclidean Steiner Trees.
J. Glob. Optim., 2006

3-star factors in random <i>d</i>-regular graphs.
Eur. J. Comb., 2006

On the Independent Domination Number of Random Regular Graphs.
Comb. Probab. Comput., 2006

Encores on Cores.
Electron. J. Comb., 2006

Analysis of Algorithms on the Cores of Random Graphs.
Proceedings of the Approximation, 2006

2005
The acyclic edge chromatic number of a random <i>d</i>-regular graph is <i>d</i> + 1.
J. Graph Theory, 2005

Counting connected graphs inside-out.
J. Comb. Theory B, 2005

Random <i>k</i>-Sat: A Tight Threshold For Moderately Growing <i>k</i>.
Comb., 2005

Connectivity for Wireless Agents Moving on a Cycle or Grid.
Proceedings of the STACS 2005, 2005

2004
Avoidance of a giant component in half the edge set of a random graph.
Random Struct. Algorithms, 2004

Hamiltonian decompositions of random bipartite regular graphs.
J. Comb. Theory B, 2004

To Adrian Bondy and U. S. R. Murty.
J. Comb. Theory B, 2004

Random Hypergraph Processes with Degree Restrictions.
Graphs Comb., 2004

Short Cycles in Random Regular Graphs.
Electron. J. Comb., 2004

Computation of the Bisection Width for Random d-Regular Graphs.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

2003
Bounds on the max and min bisection of random cubic and random 4-regular graphs.
Theor. Comput. Sci., 2003

On the probability of independent sets in random graphs.
Random Struct. Algorithms, 2003

A PTAS for the sparsest 2-spanner of 4-connected planar triangulations.
J. Discrete Algorithms, 2003

Asymptotic enumeration of sparse graphs with a minimum degree constraint.
J. Comb. Theory A, 2003

Enumeration of <i>P</i> <sub>4</sub>-Free Chordal Graphs.
Graphs Comb., 2003

Analysis of greedy algorithms on graphs with bounded degrees.
Discret. Math., 2003

Connectedness Of The Degree Bounded Star Process.
Comb. Probab. Comput., 2003

Sharp Concentration of the Number of Submaps in Random Planar Triangulations.
Comb., 2003

Analytic Graph Theory.
Proceedings of the Handbook of Graph Theory., 2003

2002
Minimum independent dominating sets of random cubic graphs.
Random Struct. Algorithms, 2002

Decycling numbers of random regular graphs.
Random Struct. Algorithms, 2002

Asymptotic Enumeration Of Graphs With A Given Upper Bound On The Maximum Degree.
Comb. Probab. Comput., 2002

Permutation Pseudographs And Contiguity.
Comb. Probab. Comput., 2002

The Number of Labeled 2-Connected Planar Graphs.
Electron. J. Comb., 2002

Bisection of Random Cubic Graphs.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

2001
Hamilton cycles containing randomly selected edges in random regular graphs.
Random Struct. Algorithms, 2001

Random regular graphs of high degree.
Random Struct. Algorithms, 2001

A polynomial algorithm for a constrained traveling salesman problem.
Networks, 2001

Counting 5-connected planar triangulations.
J. Graph Theory, 2001

Gradient-constrained minimum networks. I. Fundamentals.
J. Glob. Optim., 2001

Regular Graphs with No Homomorphisms onto Cycles.
J. Comb. Theory B, 2001

Random Matchings Which Induce Hamilton Cycles and Hamiltonian Decompositions of Random Regular Graphs.
J. Comb. Theory B, 2001

Linear Arboricity and Linear k-Arboricity of Regular Graphs.
Graphs Comb., 2001

2000
The Distribution of the Maximum Vertex Degree in Random Planar Maps.
J. Comb. Theory A, 2000

The asymptotic number of graphs with a restriction on the maximum degree.
Electron. Notes Discret. Math., 2000

The Difficulty of Constructing a Leaf-labelled Tree Including or Avoiding Given Subtrees.
Discret. Appl. Math., 2000

Random Star Processes.
Comb. Probab. Comput., 2000

Covering regular graphs with forests of small trees.
Australas. J Comb., 2000

Maximum Induced Matchings of Random Cubic Graphs.
Proceedings of the Computing and Combinatorics, 6th Annual International Conference, 2000

1999
The Size of the Largest Components in Random Planar Maps.
SIAM J. Discret. Math., 1999

Generating Random Regular Graphs Quickly.
Comb. Probab. Comput., 1999

The Asymptotic Number of Set Partitions with Unequal Block Sizes.
Electron. J. Comb., 1999

1998
Factorisation of regular graphs into forests of short paths.
Discret. Math., 1998

More on the linear k-arboricity of regular graphs.
Australas. J Comb., 1998

A Tree-Based Mergesort.
Acta Informatica, 1998

Geometric Separator Theorems & Applications.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
Steiner Trees for Terminals Constrained to Curves.
SIAM J. Discret. Math., 1997

1-Factorizations of random regular graphs.
Random Struct. Algorithms, 1997

The degree sequence of a random graph. I. The models.
Random Struct. Algorithms, 1997

Asymptotic Enumeration of Convex Polygons.
J. Comb. Theory A, 1997

Full Minimal Steiner Trees on Lattice Sets.
J. Comb. Theory A, 1997

Minimal Steiner Trees for Rectangular Arrays of Lattice Points.
J. Comb. Theory A, 1997

Shortest networks on spheres.
Proceedings of the Network Design: Connectivity and Facilities Location, 1997

1996
The perturbation method and triangle-free random graphs.
Random Struct. Algorithms, 1996

Sudden Emergence of a Giant<i>k</i>-Core in a Random Graph.
J. Comb. Theory B, 1996

Minimal Steiner Trees for 2<sup>k</sup>×2<sup>k</sup> Square Lattices.
J. Comb. Theory A, 1996

Generating and Counting Hamilton Cycles in Random Regular Graphs.
J. Algorithms, 1996

On the linear k-arboricity of cubic graphs.
Discret. Math., 1996

Reconstruction of Rooted Trees From Subtrees.
Discret. Appl. Math., 1996

A Family of Perfect Hashing Methods.
Comput. J., 1996

1995
Largest 4-Connected Components of 3-Connected Planar Triangulations.
Random Struct. Algorithms, 1995

Almost All Maps Are Asymmetric.
J. Comb. Theory B, 1995

Long Cycles and 3-Connected Spanning Subgraphs of Bounded Degree in 3-Connected <i>K</i><sub>1, <i>d</i></sub>-Free Graphs.
J. Comb. Theory B, 1995

1994
Almost All Regular Graphs Are Hamiltonian.
Random Struct. Algorithms, 1994

Spanning eulerian subgraphs of bounded degree in triangulations.
Graphs Comb., 1994

Edge Crossings in Drawings of Bipartite Graphs.
Algorithmica, 1994

1993
Infinite highly arc transitive digraphs and universal covering digraphs.
Comb., 1993

Performance Guarantees for Motion Planning with Temporal Uncertainty.
Aust. Comput. J., 1993

Graphs, Hypergraphs and Hashing.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1993

1992
Almost All Cubic Graphs Are Hamiltonian.
Random Struct. Algorithms, 1992

Enumeration of Almost-Convex Polygons on the Square Lattice.
Random Struct. Algorithms, 1992

Longest cycles in 3-connected planar graphs.
J. Comb. Theory B, 1992

Random Graph Processes with Degree Restrictions.
Comb. Probab. Comput., 1992

Sorting and/by Merging Finger Trees.
Proceedings of the Algorithms and Computation, Third International Symposium, 1992

1991
Asymptotic enumeration by degree sequence of graphs with degress o(n<sup>1/2</sup>).
Comb., 1991

1990
On the Distribution of Lengths of Evolutionary Trees.
SIAM J. Discret. Math., 1990

Cycles containing matchings and pairwise compatible euler tours.
J. Graph Theory, 1990

Removable edges in 3-connected graphs.
J. Graph Theory, 1990

Uniform Generation of Random Regular Graphs of Moderate Degree.
J. Algorithms, 1990

Asymptotic Enumeration by Degree Sequence of Graphs of High Degree.
Eur. J. Comb., 1990

Fixed edge-length graph drawing is NP-hard.
Discret. Appl. Math., 1990

k-walks of graphs.
Australas. J Comb., 1990

1989
Bounds on the measurable chromatic number of R<sup>n</sup>.
Discret. Math., 1989

1988
The asymptotic number of rooted nonseparable maps on a surface.
J. Comb. Theory A, 1988

Random Triangulations of the Plane.
Eur. J. Comb., 1988

1987
Generating Random Unlabelled Graphs.
SIAM J. Comput., 1987

Ménage numbers, bijections and P-recursiveness.
Discret. Math., 1987

Optimal Worst Case Trees.
Acta Informatica, 1987

1986
Extremal clique coverings of complementary graphs.
Comb., 1986

The asymptotic number of acyclic diagraphs I.
Comb., 1986

1985
Enumeration of cyclically 4-connected cubic graphs.
J. Graph Theory, 1985

Cataloguing the graphs on 10 vertices.
J. Graph Theory, 1985

Regular factors of regular graphs.
J. Graph Theory, 1985

Counting labelled chordal graphs.
Graphs Comb., 1985

The number of loopless planar maps.
Discret. Math., 1985

1984
Isomorphic factorizations VII. Regular graphs and tournaments.
J. Graph Theory, 1984

Generating Random Regular Graphs.
J. Algorithms, 1984

Automorphisms of random graphs with specified vertices.
Comb., 1984

1983
Numbers of cubic graphs.
J. Graph Theory, 1983

1981
Counting the 10-point graphs by partition.
J. Graph Theory, 1981

The asymptotic distribution of short cycles in random regular graphs.
J. Comb. Theory B, 1981

The asymptotic connectivity of labelled regular graphs.
J. Comb. Theory B, 1981

Counting unrooted planar maps.
Discret. Math., 1981

1980
Number of labeled 4-regular graphs.
J. Graph Theory, 1980

1979
The exponential generating function of labelled blocks.
Discret. Math., 1979

1978
Achiral plane trees.
J. Graph Theory, 1978

1977
Counting labelled 3-connected graphs.
J. Graph Theory, 1977

The divisibility theorem for isomorphic factorizations of complete graphs.
J. Graph Theory, 1977


  Loading...