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, Ser. 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, Ser. 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, Ser. B, 2007
Network modelling of underground mine layout: two case studies.
Int. Trans. Oper. Res., 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
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, Ser. 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, Ser. B, 2004
To Adrian Bondy and U. S. R. Murty.
J. Comb. Theory, Ser. 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, Ser. 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
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, Ser. B, 2001
Random Matchings Which Induce Hamilton Cycles and Hamiltonian Decompositions of Random Regular Graphs.
J. Comb. Theory, Ser. 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, Ser. 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
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
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, Ser. A, 1997
Full Minimal Steiner Trees on Lattice Sets.
J. Comb. Theory, Ser. A, 1997
Minimal Steiner Trees for Rectangular Arrays of Lattice Points.
J. Comb. Theory, Ser. 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, Ser. B, 1996
Minimal Steiner Trees for 2<sup>k</sup>×2<sup>k</sup> Square Lattices.
J. Comb. Theory, Ser. 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, Ser. 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, Ser. 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, Ser. 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
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, Ser. 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
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, Ser. B, 1981
The asymptotic connectivity of labelled regular graphs.
J. Comb. Theory, Ser. 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
1977
Counting labelled 3-connected graphs.
J. Graph Theory, 1977
The divisibility theorem for isomorphic factorizations of complete graphs.
J. Graph Theory, 1977
