NOTES ON COVERING OF ARCS BY NODES IN AN UNDIRECTED GRAPH.
OPERATIONS RESEARCH CENTER UNIV OF CALIF BERKELEY
Pagination or Media Count:
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 Gomorys method is done. Author
- Operations Research