AN INTRODUCTION TO RANDOMIZED ALGORITHMS

被引：53

作者：

KARP, RM ^{[1
]}

机构：

[1] INT COMP SCI INST, BERKELEY, CA 94704 USA

来源：

DISCRETE APPLIED MATHEMATICS | 1991年 / 34卷 / 1-3期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0166-218X(91)90086-C

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Research conducted over the past fifteen years has amply demonstrated the advantages of algorithms that make random choices in the course of their execution. This paper presents a wide variety of examples intended to illustrate the range of applications of randomized algorithms, and the general principles and approaches that are of greatest use in their construction. The examples are drawn from many areas, including number theory, algebra, graph theory, pattern matching, selection, sorting, searching, computational geometry, combinatorial enumeration, and parallel and distributed computation.

引用

页码：165 / 201

页数：37

共 49 条

[1]

Adelson-Velskii M., 1962, SOV MATH DOKL, V3, P1259

[2]

ADLEMAN, 1988, RECOGNIZING PRIMES R

[3]

AJTAI M, 1987, 19TH P ACM S THEOR C, P132

[4] RANDOMIZED SEARCH-TREES [J].

ARAGON, CR ;

SEIDEL, RG .

30TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 1989, :540-545

[5]

BARANI I, 1986, 18 ANN ACM S THEOR C, P442

[6] 2 THEOREMS IN GRAPH THEORY [J].

BERGE, C .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1957, 43 (09) :842-844

[7] HOW TO GENERATE CRYPTOGRAPHICALLY STRONG SEQUENCES OF PSEUDO-RANDOM BITS [J].

BLUM, M ;

MICALI, S .

SIAM JOURNAL ON COMPUTING, 1984, 13 (04) :850-864

[8]

BRODER AZ, 1986, 18TH P ACM S THEOR C, P50

[9]

Chazelle B., 1988, 29th Annual Symposium on Foundations of Computer Science (IEEE Cat. No.88CH2652-6), P590, DOI 10.1109/SFCS.1988.21975

[10]

Clarkson K. L., 1988, 29th Annual Symposium on Foundations of Computer Science (IEEE Cat. No.88CH2652-6), P452, DOI 10.1109/SFCS.1988.21961

← 1 2 3 4 5 →