Accession Number:

ADA091122

Title:

Recent Developments in the Complexity of Combinatorial Algorithms

Descriptive Note:

Technical rept.

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1980-06-01

Pagination or Media Count:

31.0

Abstract:

Several major advances in the area of combinatorial algorithms include improved algorithms for matrix multiplication and maximum network flow, a polynomial-time algorithm for linear programming, and steps toward a polynomial-time algorithm for graph isomorphism. This paper surveys these results and suggests directions for future research. Included is a discussion of recent work by the author and his students on dynamic dictionaries, network flow problems, and related questions.

Subject Categories:

  • Theoretical Mathematics
  • Computer Programming and Software
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE