Abstract:
A combinatorial structure (fibroid) is introduced which is a generalization of the matroid and structure of paths in a graph without oriented cycles. A bifurcation-greedy (BG) algorithm is described for search for an optimal set whose particular cases are the greedy algorithm and the Ford algorithm for search for the shortest path. For the class of feasible functions which includes linear functions, the BG-algorithm finds optimal solutions on the fibroid. With some additional assumptions correct operation of the BG-algorithm on a system of sets for a class of linear functions is evidence that the system is a fibroid.