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):

Report Date:

1966-07-01

Pagination or Media Count:

20.0

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 Gomorys method is done. Author

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE