摘要:

AbstractRandom unary predicatesUon [n] holding with probabilitypare examined with respect to sentencesAin a first‐order language containingUand “less than.” Whenp=p(n)satisfiesnk+1≪ 1 ≪npkit is shown that Pr[A] approaches a limit dependent only onkandA. In a similar circular model the limit is shown to be zero or one. © 1994 John Wiley

ISSN:1042-9832    

DOI:10.1002/rsa.3240050302

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

年代:1994

数据来源: WILEY

摘要:

AbstractConsider a random graphGcomposed of a Hamiltonian cycle onnlabeled vertices anddnrandom edges that “high” the cycle. Is it possible to unravel the structures, that is, to efficiently find a Himiltonian cycle inG? We describe anO(n3logn)‐step algorithmAfor this purpose, and prove that it succeeds almost surely. Part one ofAproperly covers the “trouble spots” ofGby a collection of disjoint paths. (This is the hard part to analyze). Part two ofAextends this cover to a full cycle by the rotation‐extension technique which is already classical for such problems. © 1994 John Wil

ISSN:1042-9832    

DOI:10.1002/rsa.3240050303

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

年代:1994

数据来源: WILEY

摘要:

AbstractPick a tree uniformly at random from among all unlabeled trees onnvertices, and let Xnbe the maximum of the degrees of its vertices. For any fixed integerd,asn→∞, where μn=c1logn, where {μn} : = μn– ⌊μ⌋ denotes the fractional part of μnand whereco,c1, and η∞are knnown constants, givenb approximately byc0= 3.262 …,c1= 0.9227 …, and η∞= 0.3383….

ISSN:1042-9832    

DOI:10.1002/rsa.3240050304

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

年代:1994

数据来源: WILEY

摘要:

AbstractWe obtain the firstNCalgorithm for the low‐diameter graph decomposition problem on arbitrary graphs. Our algorithm runs inO(log5(n)) time, and usesO(n2) processors. © 1994 John Wiley&Sons, I

ISSN:1042-9832    

DOI:10.1002/rsa.3240050305

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

年代:1994

数据来源: WILEY

摘要:

AbstractWe consider the problem of computing with faulty components in the context of the Boolean decision tree model, in which cost is measured by the number of input bits queried, and the responses to queries are faulty with a fixed probability. We show that iffcan be represented ink‐DNF form and inj‐CNF form, thenO(nlog(min(k, j)/q)) queries suffice to computefwith error probability less thanq, wherenis the number of input bits. © 1994 John Wiley&Sons,

ISSN:1042-9832    

DOI:10.1002/rsa.3240050306

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

年代:1994

数据来源: WILEY

摘要:

AbstractIt is well‐known that not all instances of the stable roommates problem admit a stable matching. Here we establish the first nontrivial upper bound on the limiting behavior ofPn, the probability that a random roommates instance of sizenhas a stable matching, namely,limn→∞Pn⩽e1/2/2 (=0.8244…). © 1994 John Wiley

ISSN:1042-9832    

DOI:10.1002/rsa.3240050307

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

年代:1994

数据来源: WILEY

ISSN:1042-9832    

DOI:10.1002/rsa.3240050301

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

年代:1994

数据来源: WILEY