A matroid algorithm and its application to the efficient solution of two optimization problems on graphs

A matroid algorithm and its application to the efficient solution of two optimization problems on graphs

0.00 Avg rating0 Votes
Article ID: iaor1988671
Country: Netherlands
Volume: 42
Issue: 3
Start Page Number: 471
End Page Number: 487
Publication Date: Dec 1988
Journal: Mathematical Programming
Authors: , ,
Abstract:

The authors address 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, and they apply it to two optimization problems on graphs. When applied to the weighted bipartite matching problem, the present algorithm has complexity O(ℝEℝℝVℝ+ℝV2logℝ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 colour i in the tree, for each i. The present algorithm for this problem has complexity O(ℝEℝℝVℝ+m2Vℝ+mV2). 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 the present algorithm is O(ℝVℝℝEℝ+ℝV*ℝℝV2). Finally, the authors discuss a new relaxation of the traveling salesman problem.

Reviews

Required fields are marked *. Your email address will not be published.