摘要:

AbstractUniform random mappings of ann‐element set to itself have been much studied in the combinatorial literature. We introduce a new technique, which starts by specifying a coding of mappings aswalkswith ± 1 steps. The uniform random mapping is thereby coded as a nonuniform random walk, and our main result is that asn→∞ the random walk rescales to reflecting Brownian bridge. This result encompasses a large number of limit theorems for “global” characteristics of uniform random mappings. © 1994 John Wile

ISSN:1042-9832    

DOI:10.1002/rsa.3240050402

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

ISSN:1042-9832    

DOI:10.1002/rsa.3240050403

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

摘要:

AbstractIn this paper we consider the component structure of decomposable combinatorial objects, both labeled and unlabeled, from a probabilistic point of view. In both cases we show that when the generating function for the components of a structure is a logarithmic function, then the joint distribution of the normalized order statistics of the component sizes of a random object of sizencoverges to the Poisson–Dirichlet distribution on the simplex ∇{{xi}: Σxi= 1x1⩾x2⩾ …︁ ⩾ 0}. This result complements recent results obtained by Flajolet and Soria on the total number of components in a random combinatorial structure. © 1994 John

ISSN:1042-9832    

DOI:10.1002/rsa.3240050404

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

摘要:

AbstractWe use the technique of divide‐and‐conquer to construct a rectilinear Steiner minimal tree on a set of sites in the plane. A well‐known optimal algorithm for this problem by Dreyfus and Wagner [10] is used to solve the problem in the base case. The run time of our optimal algorithm is probabilistic in nature: for all ϵ>0, there existsb>0 such that Prob[T(n)>2b√nlogn]>1–ϵ, for n logn>1 – ϵ, fornsites uniformly distributed on a rectangle. The key fact in the run‐time argument is the existence of probable bounds on the number of edges of an optimal tree crossing our subdivision lines. We can test these bounds in low‐degree polynomial time for any given set of sites. © 1994 J

ISSN:1042-9832    

DOI:10.1002/rsa.3240050405

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

摘要:

AbstractSuppose thatntokens are arbitrarily placed on thennodes of a graph. At each parallel step one token may be moved from each node to an adjacent node. An algorithm for thenear‐perfect token distributionproblem redistributes the tokens in a finite number of steps, so that, at the end, no more thanO(1) tokens reside at each node. (In perfect distribution, at the end, exactly one token resides at each node.) In this paper we present a simple algorithm that works for allextrovertgraphs, a new property which we define and study. In terms of connectivity requirements, extrovert graphs are roughly in‐between expanders and compressors. Our results lead to an optimal solution for the near‐perfect token distribution problem on almost all cubic graphs. The new solution is conceptually simpler than previous algorithms, and applies to graphs of minimum possible degree. © 1994 John Wiley&Son

ISSN:1042-9832    

DOI:10.1002/rsa.3240050406

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

摘要:

AbstractWe refine the method of our previous paper [2] which gave upper bounds for the critical probability in two‐dimensional oriented percolation. We use our refinement to show that\documentclass{article}\pagestyle{empty}\begin{document}$$p_c \, < \,0.6735.$$\end{document}© 1994 John Wiley&Sons, I

ISSN:1042-9832    

DOI:10.1002/rsa.3240050407

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

摘要:

AbstractRecently Sharir and Welzl described a randomized algorithm for a certain class of optimization problems (including linear programming), and then a subexponential bound for the expected running time was established. We give an example of an (artificial) optimization problem fitting into the Sharir–Welzl framework for which the running time is close to the upper bound, thus showing that the analysis of the algorithm cannot be much improved without stronger assumptions on the optimization problem and/or modifying the algorithm. Further we describe results of computer simulations for a specific linear programming problem, which indicate that “one‐permutation” and “move‐to‐front” variants of the Sharir–Welzl algorithm may sometimes perform much worse than the algorithm itself. © 1994 Jo

ISSN:1042-9832    

DOI:10.1002/rsa.3240050408

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY

ISSN:1042-9832    

DOI:10.1002/rsa.3240050401

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1994

数据来源: WILEY