Zobrazeno 1 - 10
of 260
pro vyhledávání: '"Wormald, Nicholas"'
Autor:
Southwell, Angus, Wormald, Nicholas
We study a random graph $G$ with given degree sequence $\boldsymbol{d}$, with the aim of characterising the degree sequence of the subgraph induced on a given set $S$ of vertices. For suitable $\boldsymbol{d}$ and $S$, we show that the degree sequenc
Externí odkaz:
http://arxiv.org/abs/2303.08339
We give an algorithm that generates a uniformly random contingency table with specified marginals, i.e. a matrix with non-negative integer values and specified row and column sums. Such algorithms are useful in statistics and combinatorics. When $\De
Externí odkaz:
http://arxiv.org/abs/2104.09413
In the $\left(1:b\right)$ component game played on a graph $G$, two players, Maker and Breaker, alternately claim~$1$ and~$b$ previously unclaimed edges of $G$, respectively. Maker's aim is to maximise the size of a largest connected component in her
Externí odkaz:
http://arxiv.org/abs/2012.08821
In this paper we provide an algorithm that generates a graph with given degree sequence uniformly at random. Provided that $\Delta^4=O(m)$, where $\Delta$ is the maximal degree and $m$ is the number of edges,the algorithm runs in expected time $O(m)$
Externí odkaz:
http://arxiv.org/abs/1905.03446
Autor:
Leckey, Kevin, Wormald, Nicholas
We obtain results on the limiting distribution of the six-length of a random functional graph, also called a functional digraph or random mapping, with given in-degree sequence. The six-length of a vertex $v\in V$ is defined from the associated mappi
Externí odkaz:
http://arxiv.org/abs/1803.02667
Autor:
Gao, Pu, Wormald, Nicholas
We give a linear-time algorithm that approximately uniformly generates a random simple graph with a power-law degree sequence whose exponent is at least 2.8811. While sampling graphs with power-law degree sequence of exponent at least 3 is fairly eas
Externí odkaz:
http://arxiv.org/abs/1709.02674
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Gao, Pu, Wormald, Nicholas
We develop a new approach for uniform generation of combinatorial objects, and apply it to derive a uniform sampler REG for d-regular graphs. REG can be implemented such that each graph is generated in expected time O(nd^3), provided that d=o(n^{1/2}
Externí odkaz:
http://arxiv.org/abs/1511.01175
Autor:
Pralat, Pawel, Wormald, Nicholas
In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph $G$ is called the cop number of $G$. The biggest open conjecture in this area is the one
Externí odkaz:
http://arxiv.org/abs/1510.03003
Autor:
Gao, Pu, Wormald, Nicholas
In this paper, we asymptotically enumerate graphs with a given degree sequence d=(d_1,...,d_n) satisfying restrictions designed to permit heavy-tailed sequences in the sparse case (i.e. where the average degree is rather small). Our general result re
Externí odkaz:
http://arxiv.org/abs/1404.1250