
Accession Number : AD0636451
Title : NOTES ON COVERING OF ARCS BY NODES IN AN UNDIRECTED GRAPH.
Descriptive Note : Research rept.
Corporate Author : OPERATIONS RESEARCH CENTER UNIV OF CALIF BERKELEY
Personal Author(s) : Lorentzen, LarsChr
Report Date : JUL 1966
Pagination or Media Count : 20
Abstract : 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)
Descriptors : (*LINEAR PROGRAMMING, *GRAPHICS), ALGORITHMS, NUMBERS, OPTIMIZATION, OPERATIONS RESEARCH
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE