Paper Info
Title
A matroid algorithm and its application to the efficient solution of two optimization problems on graphs.
Abstract
We address the problem of finding a minimum weight baseB of a matroid when, in addition, each element of the matroid is colored with one ofm colors and there are upper and lower bound restrictions on the number of elements ofB with colori, fori = 1, 2,?,m. This problem is a special case of matroid intersection. We present an algorithm that exploits the special structure, and we apply it to two optimization problems on graphs. When applied to the weighted bipartite matching problem, our algorithm has complexity O(|E?V|+|V|2log|V|). HereV denotes the node set of the underlying bipartite graph, andE denotes its edge set. The second application is defined on a general connected graphG = (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 colori in the tree, for eachi. Our algorithm for this problem has complexity O(|E?V|+m2|V|+ m|V|2). A special case of this constrained spanning tree problem occurs whenV* is a set of pairwise nonadjacent nodes ofG. One must find a minimum weight spanning tree with upper and lower bound restrictions on the degree of each node ofV*. Then the complexity of our algorithm is O(|V?E|+|V*?V|2). Finally, we discuss a new relaxation of the traveling salesman problem.
Year
DOI
Venue
1988
10.1007/BF01589417
Math. Program.
Keywords
DocType
Volume
efficient solution,optimization problem,matroid algorithm
Journal
42
Issue
ISSN
Citations 
1-3
0025-5610
13
PageRank 
References 
Authors
1.17
9
3
Name
Order
Citations
PageRank
C Brezovec1362.71
Gérard Cornuéjols22390279.95
F. Glover3131.17