We consider the following common network analysis problem: given a degree sequence d = (d1,…, dn) ∈ ℕn return a uniform sample from the ensemble of all simple graphs with matching degrees. In practice, the problem is typically solved using Markov Chain Monte Carlo approaches, such as Edge-Switching or Curveball, even if no practical useful rigorous bounds are known on their mixing times. In contrast, Arman et al. sketch INC-PoWERLAW, a novel and much more involved algorithm capable of generating graphs for power-law bounded degree sequences with γ ⪆ 2.88 in expected linear time. For the first time, we give a complete description of the algorithm and add novel switchings. To the best of our knowledge, our open-source implementation of INC-POWERLAW is the first practical generator with rigorous uniformity guarantees for the aforementioned degree sequences. In an empirical investigation, we find that for small average-degrees INC-POWERLAW is very efficient and generates graphs with one million nodes in less than a second. For larger average-degrees, parallelism can partially mitigate the increased running-time.

Abstract Let denote the distance matrix of n objects, and let T be an unrooted binary tree in which the leaves denote those n objects. We want to find such a tree with the constraint that the edge weights are nonnegative where the distances between the leaves best estimate their corresponding values in D. Accordingly, we have adopted the residual sum of squares (RSS) criterion to minimize the discrepancy between the distance between leaves in the tree and their corresponding distance in D. For this optimization problem, we have designed an iterated local search (ILS) scheme based on the nearest neighbor interchange (NNI) operation to search the neighborhood.

We want to find a tree where the path length between any two vertices on this tree is as close as possible to their corresponding distance in the complete weighted graph of vertices upon which the tree is built.We use the residual sum of squares as the optimality criterion to formulate this problem, and use the Cholesky decomposition to solve the system of linear equations to optimize weights of a given tree.We also use two metaheuristics, namely Simulated Annealing (SA) and Iterated Local Search (ILS) to optimize the tree structure.Our results suggest that SA and ILS both perform well at finding the optimal tree structure when the dispersion of distances in the complete graph is large.However, when the dispersion of distances is small, only ILS has a solid performance.

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 easy, and many samplers work efficiently in this case, the problem becomes dramatically more difficult when the exponent drops below 3; ours is the first provably practicable sampler for this case. We also show that with an appropriate rejection scheme, our algorithm can be tuned into an exact uniform sampler. The running time of the exact sampler is O(n2.107) with high probability, and O(n4.081) in expectation.

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(\sqrt{n})$. Our result significantly improves the previously best uniform sampler, which works efficiently only when $d=O(n^{1/3})$, with essentially the same running time for the same $d$. We also give a linear-time approximate sampler REG*, which generates a random $d$-regular graph whose distribution differs from the uniform by $o(1)$ in total variation distance, when $d=o(\sqrt{n})$.

The asynchronous push&pull protocol, a randomized distributed algorithm for spreading a rumor in a graph $G$, is defined as follows. Independent exponential clocks of rate 1 are associated with the vertices of $G$, one to each vertex. Initially, one vertex of $G$ knows the rumor. Whenever the clock of a vertex $x$ rings, it calls a random neighbor $y$: if $x$ knows the rumor and $y$ does not, then $x$ tells $y$ the rumor (a push operation), and if $x$ does not know the rumor and $y$ knows it, $y$ tells $x$ the rumor (a pull operation). The average spread time of $G$ is the expected time it takes for all vertices to know the rumor, and the guaranteed spread time of $G$ is the smallest time $t$ such that with probability at least $1 - 1/n$, after time $t$ all vertices know the rumor. The synchronous variant of this protocol, in which each clock rings precisely at times $1,2,\dots$, has been studied extensively. We prove the following results for any $n$-vertex graph: In either version, the average spread time is at most linear even if only the pull operation is used, and the guaranteed spread time is within a logarithmic factor of the average spread time, so it is $O(n \log n)$. In the asynchronous version, both the average and guaranteed spread times are $\Omega(\log n)$. We give examples of graphs illustrating that these bounds are best possible up to constant factors. We also prove the first analytical relationships between the guaranteed spread times in the two versions. First, in all graphs the guaranteed spread time in the asynchronous version is within an $O(\log n)$ factor of that in the synchronous version, and this is tight. Next, we find examples of graphs whose asynchronous spread times are logarithmic, but the synchronous versions are polynomially large. Finally, we show for any graph that the ratio of the guaranteed synchronous spread time to the guaranteed asynchronous spread time is $O\big(n^{2/3}\big)$.

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(nd3), provided that d = o(√n). Our result significantly improves the previously best uniform sampler, which works efficiently only when d = O(n1/3), with essentially the same running time for the same d. We also give a linear-time approximate sampler REG*, which generates a random d-regular graph whose distribution differs from the uniform by o(1) in total variation distance, when d = o(√n).

The asynchronous push&pull protocol, a randomized distributed algorithm for spreading a rumour in a graph G, is defined as follows. Independent exponential clocks of rate 1 are associated with the vertices of G, one to each vertex. Initially, one vertex of G knows the rumour. Whenever the clock of a vertex x rings, it calls a random neighbour y: if x knows the rumour and y does not, then x tells y the rumour (a push operation), and if x does not know the rumour and y knows it, y tells x the rumour (a pull operation). The average spread time of G is the expected time it takes for all vertices to know the rumour, and the guaranteed spread time of G is the smallest time t such that with probability at least 1 - 1/n, after time t all vertices know the rumour. The synchronous variant of this protocol, in which each clock rings precisely at times 1,2,..., has been studied extensively.

We prove logarithmic upper bounds for the diameters of the random-surfer Webgraph model and the PageRank-based selection Webgraph model, confirming the small-world phenomenon holds for them. In the special case when the generated graph is a tree, we get close lower and upper bounds for the diameters of both models.

The vertex isoperimetric number of a graph $G=(V,E)$ is the minimum of the ratio $|\partial_{V}U|/|U|$ where $U$ ranges over all nonempty subsets of $V$ with $|U|/|V|\le u$ and $\partial_{V}U$ is the set of all vertices adjacent to $U$ but not in $U$. The analogously defined edge isoperimetric number---with $\partial_{V}U$ replaced by $\partial_{E}U$, the set of all edges with exactly one endpoint in $U$---has been studied extensively. Here we study random regular graphs. For the case $u=1/2$, we give asymptotically almost sure lower bounds for the vertex isoperimetric number for all $d\ge3$. Moreover, we obtain a lower bound on the asymptotics as $d\to\infty$. We also provide asymptotically almost sure lower bounds on $|\partial_{E}U|/|U|$ in terms of an upper bound on the size of $U$ and analyze the bounds as $d\to\infty$.

We improve Łuczak's upper bound on the length of the longest cycle in the random graph ${\cal G}(n,M)$ in the “supercritical phase,” where $M=n/2+s$ and $s=o(n)$ but $n^{2/3}=o(s)$. The new upper bound is $(6.958+o(1))s^2/n$ with probability $1-o(1)$ as $n\to\infty$. Letting $c=1+2s/n$, the equivalence between ${\cal G}(n,p)$ and ${\cal G}(n,M)$ implies the same result for ${\cal G}(n,p)$, where $p=c/n$, $c\to 1$, $c-1 =\omega(n^{-1/3})$.

Let h>w>0 be two fixed integers. Let H be a random hypergraph whose hyperedges are all of cardinality h. To w-orient a hyperedge, we assign exactly w of its vertices positive signs with respect to the hyperedge, and the rest negative. A (w,k)-orientation of H consists of a w-orientation of all hyperedges of H, such that each vertex receives at most k positive signs from its incident hyperedges. When k is large enough, we determine the threshold of the existence of a (w,k)-orientation of a random hypergraph. The (w,k)-orientation of hypergraphs is strongly related to a general version of the off-line load balancing problem. The graph case, when h=2 and w=1, was solved recently by Cain, Sanders and Wormald and independently by Fernholz and Ramachandran, thereby settling a conjecture made by Karp and Saks. Motivated by a problem of cuckoo hashing, the special hypergraph case with w=k=1, was solved in three separate preprints dating from October 2009, by Frieze and Melsted, by Fountoulakis and Panagiotou, and by Dietzfelbinger, Goerdt, Mitzenmacher, Montanari, Pagh and Rink.

A model for cleaning a graph with brushes was recently introduced. We consider the minimum number of brushes needed to clean d-regular graphs in this model, focusing on the asymptotic number for random d-regular graphs. We use a degree-greedy algorithm to clean a random d-regular graph on n vertices (with $dn$ even) and analyze it using the differential equations method to find the (asymptotic) number of brushes needed to clean a random d-regular graph using this algorithm (for fixed d). We further show that for any d-regular graph on n vertices at most $n(d+1)/4$ brushes suffice and prove that, for fixed large d, the minimum number of brushes needed to clean a random d-regular graph on n vertices is asymptotically almost surely $\frac{n}{4}(d+o(d))$, thus solving a problem raised in [M.E. Messinger, R.J. Nowakowski, P. Prałat, and N. Wormald, Cleaning random d-regular graphs with brushes using a degree-greedy algorithm, in Combinatorial and Algorithmic Aspects of Networking, Lecture Notes in Comput. Sci. 4852, Springer, Berlin-Heidelberg, 2007, pp. 13–26].

We present a model of the establishment and maintenance of communication between mobile agents. We assume that the agents move through a fixed environment modeled by a motion graph and are able to communicate if they are within distance at most d of each other. As the agents move randomly, we analyze the evolution in time of the connectivity between a set of w agents, asymptotically for a large number N of vertices, when w also grows large. The particular topologies of the environment we study here are the cycle and the toroidal grid.

Abstract We give a polynomial‐time algorithm for finding a solution to the Traveling Salesman Problem when the points given are constrained to lie on a fixed set of smooth curves of finite length. © 2001 John Wiley & Sons, Inc.

Bender, Richmond, and Wormald showed that in almost all planar 3-connected triangulations (or dually, 3-connected cubic maps) with n edges, the largest 4-connected triangulation (or dually, the largest cyclically 4-edge-connected cubic component) has about n/2 edges [ Random Structures Algorithms, 7 (1995), pp. 273--285]. In this paper, we derive some general results about the size of the largest component and apply them to a variety of types of planar maps.

We find a large number of "geometric separator theorems" such as: I: Given N disjoint isooriented squares in the plane, there exists a rectangle with /spl les/2N/3 squares inside, /spl les/2N/3 squares outside, and /spl les/(4+0(1))/spl radic/N partly in & out. II: There exists a rectangle that is crossed by the minimal spanning tree of N sites in the plane at /spl les/(4/spl middot/3/sup 1/4/+0(1))/spl radic/N points, having /spl les/2N/3 sites inside and outside. These theorems yield a large number of applications, such as subexponential algorithms for traveling salesman tour and rectilinear Steiner minimal tree in R/sup d/, new point location algorithms, and new upper and lower bound proofs for "planar separator theorems".

We give a polynomial time algorithm for solving the Euclidean Steiner tree problem when the terminals are constrained to lie on a fixed finite set of disjoint finite-length compact simple smooth curves. The problem is known to be NP-hard in general. We also show it to be NP-hard if the terminals lie on two parallel infinite lines or on a bent line segment provided the bend has an angle of less than $120^\circ$.

Minimal perfect hash functions are used for memory efficient storage and fast retrieval of items from static sets. We present an infinite family of efficient and practical algorithms for generating order preserving minimal perfect hash functions. We show that almost all members of the family construct space and time optimal order preserving minimal perfect hash functions, and we identify the one with minimum constants. Members of the family generate a hash function in two steps. First a special kind of function into an r-graph is computed probabilistically. Then this function is refined deterministically to a minimal perfect has function. We give strong theoretical evidence that the first step uses linear random time. The second step runs in linear deterministic time. The family not only has theoretical importance, but also offers the fastest known methods for generating perfect hash functions.

This paper presents the results of the authors’ investigation of a combinatorial problem arising from the study of evolutionary trees. In graph theoretic terms it can be expressed as a problem of colouring vertices of a binary tree. For a given colouring of the pendant vertices of a binary tree there is a simple algorithm for assigning colours to internal vertices minimising the number of edges of the tree whose end vertices have differing colours. This minimal number is called the length of the tree. The question posed is: For given numbers of pendant vertices of assigned colours, how many trees of a particular length can be constructed on those vertices? This question is answered in two special cases. Answers to this problem are needed to establish the distribution of lengths of evolutionary trees, by which the significance of the maximum parsimony principle for selecting evolutionary trees can be judged.

Unlabelled graphs on n vertices can be generated uniformly at random, without calculating the total numbers of such graphs, but by using asymptotic enumeration results. For large n, the process is very efficient, taking $O(n^2 )$ steps on average. In fact, for $n \geqq 50$, virtually all practical applications will require only the first step of the algorithm to be implemented. This step is almost as simple as, and has the appearance of, the random generation of labelled graphs, yet the net effect is the uniform generation of unlabelled graphs at random. By similar methods one can generate random unlabelled graphs with n vertices and m edges, in expected time $O(n^2 \sqrt m )$ for most values of m. Also, random unlabelled r-regular graphs can be generated in expected time $O(n)$ when $r \geqq 3$ is fixed, but this is only (so far) practicable for a few small values of r.