Accession Number : AD0771093

Title :   Finding a Minimum Node Cover in an Arbitrary Graph.

Descriptive Note : Research rept.,


Personal Author(s) : Balas,Egon ; Samuelsson,Haakon

Report Date : NOV 1973

Pagination or Media Count : 43

Abstract : The paper describes a node covering algorithm, i.e., a procedure for finding a smallest set of nodes covering all edges of an arbitrary graph. The algorithm is based on the concept of a dual node-clique set which allows one to identify partial covers associated with integer dual feasible solutions to the linear programming equivalent of the node covering problem. An initial partial cover with the above property is first found by a labeling procedure. Another labeling procedure then successively modifies the dual node-clique set, so that more and more edges are covered, i.e., the (primal) infeasibility of the solution is gradually reduced, while integrality and dual feasibility are preserved. When this cannot be continued, the problem is partitioned and the procedure applied to the resulting subproblems. While the steps of the algorithm correspond to sequences of dual simplex pivots, these are carried out implicitly, by labeling. The procedure is illustrated on examples, and some early computational experience is reported. The authors conclude with a discussion of potential improvements and extensions. (Author)

Descriptors :   *Linear programming, *Graphs, Simplex method, Set theory, Algorithms

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE