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 non-uniform 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