Recent Developments in the Complexity of Combinatorial Algorithms

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1980
Accession Number
ADA091122

Entities

People

  • Robert Tarjan

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • California
  • Computer Programming
  • Computer Science
  • Computers
  • Convex Programming
  • Dictionaries
  • Evolutionary Algorithms
  • Linear Programming
  • Numbers
  • Operations Research
  • Optimization
  • Polynomials
  • Real Numbers
  • Simplex Method
  • Trees (Data Structures)

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Systems Analysis and Design