摘要:

AbstractVarious Markov chains on hypercubes ℒ︁ n2are considered and their spectral representations are presentend in terms of Kronecker products. Special attention is given to random walks on the graphs

ISSN:1042-9832    

DOI:10.1002/rsa.3240040102

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

年代:1993

数据来源: WILEY

摘要:

AbstractOur goal is to design practical sorting algorithms that require time proportional not only to the size of the input but also to the disorder in the input. Such sorting algorithms are said to beadaptive. We introduce randomization to achieve this goal; the first time randomization has used to obtain adaptive sorting algorithms. We investigate three randomized algorithms.1Randomized Merge Sort, which is expected Runs‐optimal;2Randomized Quicksort, which is Exchange‐sensitive, that is, it takes Θ(|X|[1+log(Exc(X)+1)]) time in the expected case; and3Skip Sort, whichh isInversions‐, Runs‐, andExchhange‐optimal.The three sorting algorithms are simple and practical, in contrast to previous adaptive sorting algorithms that used complex data structures. Moreover, previous claims about the performance of adaptive variants ofQuicksortwere baed only on simulation results,; our claims are based on a formal analysis. © 1993 John Wile

ISSN:1042-9832    

DOI:10.1002/rsa.3240040103

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

年代:1993

数据来源: WILEY

摘要:

AbstractGiven a sequence of indepent, uniformly distributed random letters coming from a finite alphabet, we are interested in the word (pattern) which is the last to be observed for the first time among all words of lengthn. We derive anas. result on the homogeneity of this last appearing pattern as a corollary of a more general theorem. © 1993 John Wiley&Sons, Inc

ISSN:1042-9832    

DOI:10.1002/rsa.3240040104

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

年代:1993

数据来源: WILEY

摘要:

AbstractA limit theorem is obtained for the number of components with more than one cycle that are created during the evolution of a random graph process. In particular, it is shown that the probability that the process never contains more than one such component is about 0.87 © 1993 John Wiley&Sons, Inc

ISSN:1042-9832    

DOI:10.1002/rsa.3240040105

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

年代:1993

数据来源: WILEY

摘要:

AbstractThe size Ramsey number r̂(G, H) of graphsGandHis the smallest integer r̂ such that there is a graphFwith r̂ edges and if the edge set ofFis red‐blue colored, there exists either a red copy ofGor a blue copy ofHinF. This article shows that r̂(Tnd, Tnd) ⩽c·d2· n andc·n3⩽ r̂(Kn, Tnd) ⩽c(d)·n3log n for every tree Tndon n vertices. and maximal degree at most d and a complete graphKnonnvertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 Joh

ISSN:1042-9832    

DOI:10.1002/rsa.3240040106

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

年代:1993

数据来源: WILEY

摘要:

AbstractWe investigate the following process:Npeople selectblosers by flipping coins. The 0‐party continues until there are less thanblosers; then the 1‐party has to find the other losers by the same process. The average time for this process is about long2N, but this result requires rather advanced methods. Furthermore, the average size of a binary tree associated to this process and the average number of coin flippings are computed. The method used in this article can be used to give asympotical solutions of a special type of bivariate recurrences. © 1993 John Wiley&Sons,

ISSN:1042-9832    

DOI:10.1002/rsa.3240040107

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

年代:1993

数据来源: WILEY

摘要:

AbstractWe present an efficient algorithm for generating ann×nnonsingular matrix uniformly over a finite field. This algorithm is useful for several cryptographic and checking applications. Over GF[2] our algorithm runs in expected timeM(n) +O(n2), whereM(n) is the time needed to multiply twon×nmatrices, and the expected number of random bits it uses isn2+ 3. (Over other finite fields we usen2+O(1) random field elements on average.) This is more efficient than the standard method for solving this problem, both in terms of expected running time and the expected number of random bits used. The standard method is to generate randomn×nmatrices until we produce one with nonzero determinant. In contrast, our techniquedirectlyproduces a random matrixguaranteedto have nonzero determinant. We also introduce efficient algorithms for related problems such as uniformly generating singular matrices or matrices with fixed determinant. © 1993 John Wiley&Sons,

ISSN:1042-9832    

DOI:10.1002/rsa.3240040108

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

年代:1993

数据来源: WILEY

ISSN:1042-9832    

DOI:10.1002/rsa.3240040109

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

年代:1993

数据来源: WILEY

ISSN:1042-9832    

DOI:10.1002/rsa.3240040101

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

年代:1993

数据来源: WILEY