NOTES ON COVERING OF ARCS BY NODES IN AN UNDIRECTED GRAPH.

摘要

Edmonds,Johnson,and Witzgall and Zahn have given efficient algorithms for the solution of the integer linear programming problem max z =ex s.t. Ex < f , x > 0 , x integer,where e and f are vectors with all components equal to one. (This is known as the maximum matching problem). Here the author considers 'the dual integer programming problem' (the minimal covering problem):min w =pi f s.t. pi E > e ,pi integer. First a lower bound on the solution of the minimal covering is given. Then some 'cycle condition'is defined which,for some special kind of graphs (called bicactus),added as supplementary constraints to the linear programming problem will give an integer solution. Finally an algorithm is proposed to solve the minimal covering problem and a qualitative comparison of its efficiency with Gomory's method is done. (Author)