Accession Number : ADA192709

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

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 : ADA192709

Report Date : Feb 1988

Pagination or Media Count : 27

Abstract : The problem of finding a minimum weight base B of a matroid is addressed 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. An algorithm exploits special structure, and is applied to two optimization problems on graphs. When applied to the weighted bipartite matching problem, the algorithm has complexity O(/E/V/ + /V/-sq log /V/). Here V denotes the node set of the underlying bipartite graph, and E denotes its edge set. The second application is defined on a general connected graph G = (V, E) whose edges have a weight and a color. One seeks a minimum weight spanning tree with upper and lower bound restrictions on the number of edges with color i in the tree, for each i. Our algorithm for this problem has complexity O(/E/ /V/ + m-sq /V/-sq). A special case of this constrained spanning tree problem occurs when V is a set of pairwise nonadjacent nodes of G. One must find a minimum weight spanning tree with upper and lower bound restrictions on the degree of each node of V. Then the complexity of our algorithm is O(/V/ /E/ + /V/ /V/-sq). Finally, we discuss a new relaxation of the traveling salesman problem.

Descriptors :   *ALGORITHMS, *GRAPHS, COLORS, EDGES, EFFICIENCY, MATCHING, NODES, OPTIMIZATION, RELAXATION, SOLUTIONS(GENERAL), TREES, WEIGHT, WEIGHTING FUNCTIONS, PROBLEM SOLVING

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE