DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
ADA191482
Title:
Algorithms and Data Structures for an Expanded Family of Matroid Intersection Problems.
Corporate Author:
ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE
Report Date:
1987-09-01
Abstract:
Matroids are discrete mathematical structures that appear in a variety of applications. They are structures for which greedy algorithm gives an optimal solution, and when interested characterize such problems as minimum weight maximum cardinality bipartite matching. In this paper we study a class of combinatorial problems from a matroid point of view. Consider a matroid of rank n in which each element has a real-valued cost and one of d 1 colors. A class of matroid intersection problems is studied in which one of the matroids is a partition matroid that specifies that base have 9 sub k elements of color j, for j 12 1, 2, ..., d. Relationships are characterized among the solutions to the family of problems generated when the vector q sub 1, q sub,... q sub d is allowed to range over all values that sum to n. A fast algorithm is given for solving such matroid intersection problems when d is small. A characterization is presented for how the solution changes when one element changes in cost. Data structures are given for updating the solution on-line each time the cost of an arbitrary matroid element is modified. Efficient update algorithms are given for maintaining a color-constrained minimum spanning tree in either a general or a planar graph. An application for the techniques to finding a minimum spanning tree with several degree-constrained vertices is described.
Descriptive Note:
Technical rept.,
Supplementary Note:
Sponsored in part by Grant NSF-DCR83-20124.
Pages:
0055
Contract Number:
N00014-86-K-0689
Contract Number 2:
N00014-82-K-0193
File Size:
2.67MB
