
Accession Number : ADA328563
Title : Weighted Random Mappings; Properties and Applications.
Descriptive Note : Doctoral thesis,
Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Broder, Andrei Z.
PDF Url : ADA328563
Report Date : MAY 1985
Pagination or Media Count : 86
Abstract : A random mapping is a random graph where ever vertex has outdegree one. Previous work was concerned mostly with a uniform probability distribution on these mappings. In contrast, this investigation assumed a nonuniform model, where differ mappings have different probabilities. An important application is the analysis of factorization heuristic due to Pollard and Brent. The model involved is a random mapping where every vertex has indegree either 0 or d. This distribution belongs to class called permutation invariant. A study of the general properties of permutation invariant mappings combined with the analysis of this particular distribution made possible the computation of the expected running time of this factorization method, settling an open conjecture of Pollard.
Descriptors : *MATHEMATICAL MODELS, *PROBABILITY DISTRIBUTION FUNCTIONS, *HEURISTIC METHODS, ALGORITHMS, COMPUTATIONS, RANDOM VARIABLES, GRAPHS, THESES, PARALLEL PROCESSING, MATHEMATICAL PROGRAMMING, PERMUTATIONS, MAPPING(TRANSFORMATIONS).
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE