Source author record

Brendan McKay

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms math.CO

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Sandwiching random regular graphs between binomial random graphs

Kim and Vu made the following conjecture (\textit{Advances in Mathematics}, 2004): if $d\gg \log n$ , then the random $d$ -regular graph $\mathcal G(n,d)$ can asymptotically almost surely be "sandwiched" between $\mathcal G(n,p_1)$ and $\mathcal G(n,p_2)$ where $p_1$ and $p_2$ are both $(1+o(1))d/n$ . They proved this conjecture for $\log n\ll d\le n^{1/3-o(1)}$ , with a defect in the sandwiching: $\mathcal G(n,d)$ contains $\mathcal G(n,p_1)$ perfectly, but is not completely contained in $\mathcal G(n,p_2)$ . Recently, the embedding $\mathcal G(n,p_1) \subseteq \mathcal G(n,d)$ was improved by Dudek, Frieze, Ruciński and Šileikis to $d=o(n)$ . In this paper, we prove Kim--Vu's sandwich conjecture, with perfect containment on both sides, for all $d\gg n/\sqrt{\log n}$ . For $d=O(n/\sqrt{\log n})$ , we prove a weaker version of the sandwich conjecture with $p_2$ approximately equal to $(d/n)\log n$ , without any defect. In addition to sandwiching regular graphs, our results cover graphs whose degrees are asymptotically equal. The proofs rely on estimates for the probability that a random factor of a pseudorandom graph contains a given edge, which is of independent interest. As applications, we obtain new results on the properties of random graphs with given near-regular degree sequences, including Hamiltonicity and universality in subgraph containment. We also determine several graph parameters in these random graphs, such as the chromatic number, small subgraph counts, the diameter, and the independence number. We are also able to characterise many phase transitions in edge percolation on these random graphs, such as the threshold for the appearance of a giant component.

preprint2021arXiv

A Highly Scalable Labelling Approach for Exact Distance Queries in Complex Networks

Answering exact shortest path distance queries is a fundamental task in graph theory. Despite a tremendous amount of research on the subject, there is still no satisfactory solution that can scale to billion-scale complex networks. Labelling-based methods are well-known for rendering fast response time to distance queries; however, existing works can only construct labelling on moderately large networks (million-scale) and cannot scale to large networks (billion-scale) due to their prohibitively large space requirements and very long preprocessing time. In this work, we present novel techniques to efficiently construct distance labelling and process exact shortest path distance queries for complex networks with billions of vertices and billions of edges. Our method is based on two ingredients: (i) a scalable labelling algorithm for constructing minimal distance labelling, and (ii) a querying framework that supports fast distance-bounded search on a sparsified graph. Thus, we first develop a novel labelling algorithm that can scale to graphs at the billion-scale. Then, we formalize a querying framework for exact distance queries, which combines our proposed highway cover distance labelling with distance-bounded searches to enable fast distance computation. To speed up the labelling construction process, we further propose a parallel labelling method that can construct labelling simultaneously for multiple landmarks. We evaluated the performance of the proposed methods on 12 real-world networks. The experiments show that the proposed methods can not only handle networks with billions of vertices, but also be up to 70 times faster in constructing labelling and save up to 90\% of labelling space. In particular, our method can answer distance queries on a billion-scale network of around 8B edges in less than 1ms, on average.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.