Accession Number : ADA292630

Title :   Research in Graph Algorithms and Combinatorial Optimization.

Descriptive Note : Final rept. 15 Apr 91-15 Apr 94,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Plotkin, Serge

PDF Url : ADA292630

Report Date : 06 MAR 1995

Pagination or Media Count : 9

Abstract : This project focused on designing fast algorithms for basic combinational optimization problems, including maximum flow, matching, multicommodity flow, and generalized flow. Many important applications are naturally stated as variants of these problems, and hence improved algorithms for these problems immediately lead to improved algorithms for a wide variety of applications. Our goal was to improve both sequential and parallel complexity. In many applications, solving a multicommodity or a generalized flow problem is only a first step in approximately solving an NP-complete problem; in the majority of such cases there is no need to have an exact solution of the problem. One of the focuses of the project was design of efficient approximation algorithms.

Descriptors :   *OPTIMIZATION, *GRAPHS, *COMBINATORIAL ANALYSIS, ALGORITHMS, EFFICIENCY, SEQUENCES, PROBLEM SOLVING, VARIATIONS, APPROXIMATION(MATHEMATICS), FLOW, PARALLEL ORIENTATION.

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE