#### Document Type

Technical Report

#### Publication Date

Fall 10-1-1978

#### Abstract

For a given combinatorial optimization problem, the corresponding COST≤C problem is to find all solutions of cost at most C. This is closely related to the often-studied K BEST problem, which is to find the K smallest solutions in order. Typical COST≤C algorithms for graph problems (e.g., paths, matchings, spanning trees) use less space (0(m+n) instead of 0(K+m+n)) than K BEST, and are slightly faster. As an illustration, several COST≤C (and K BEST) algorithms for matchings on bipartite graphs are presented. The times are 0(K min(n^3, mn log n)), improving previous bounds. Theapproach is to reduce the matching problems to path problems on directed graphs. Lastly, a justification is given for the relatively high time bound on COST≤C for paths: A single-source problem arising in its solution is shown to be equivalent to a multi-source problem.

#### Recommended Citation

Gabow, Hal N., "Finding the Best Solutions: The Cost of ls C Problem and Finding Matchings ; CU-CS-139-78" (1978). *Computer Science Technical Reports*. 137.

http://scholar.colorado.edu/csci_techreports/137