Weighted Random Mappings; Properties and Applications.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1985
- Accession Number
- ADA328563
Entities
People
- Andrei Z. Broder
Organizations
- Stanford University