Accession Number:

ADA043362

Title:

Complexity of Combinatorial Algorithms.

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Tarjan,Robert E.

Report Date:

1977-04-01

Pagination or Media Count:

87.0

Abstract:

This paper examines recent work on the complexity of combinatorial algorithms, highlighting the aims of the work, the mathematical tools used, and the important results. Included are sections discussing ways to measure the complexity of an algorithm, methods for proving that certain problems are very hard to solve, tools useful in the design of good algorithms, and recent improvements in algorithms for solving ten representative problems. The final section suggests some directions for future research. Author

Descriptors:

• *COMPUTER PROGRAMMING
• *COMBINATORIAL ANALYSIS
• MATHEMATICAL MODELS
• ALGORITHMS
• EFFICIENCY
• PROBLEM SOLVING
• RANDOM ACCESS COMPUTER STORAGE
• TIME
• DECISION THEORY
• HEURISTIC METHODS
• COMPUTER PROGRAM VERIFICATION

Subject Categories:

• Theoretical Mathematics
• Computer Programming and Software
• Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE