Accession Number : ADA180342

Title :   A Matroid Algorithm and Its Application to the Efficient Solution of Two Optimization Problems on Graphs.

Descriptive Note : Management sciences research rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Brezovec, Carl ; Cornuejols, Gerard ; Glover, Fred

PDF Url : ADA180342

Report Date : Feb 1987

Pagination or Media Count : 22

Abstract : This document addresses the problem of finding a minimum weight base B of a matroid when, in addition, each element of the matroid is colored with one of m colors and there are upper and lower bound restrictions on the number of elements of B with color i, for i = 1,2, ..., m. This problem is a special case of matroid intersection. The authors present an algorithm that exploits the special structure. When applied to the weighted bipartite matching problem, this algorithm has complexity O(lVlcubed). In both cases, V denotes the node set of the underlying graph, and E denotes its edge set. Also discussed is a new relaxation for the traveling salesman problem.

Descriptors :   *WEIGHTING FUNCTIONS, *ALGORITHMS, SET THEORY, TREES, PROBLEM SOLVING, GRAPHS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE