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