
Accession Number : AD0771093
Title : Finding a Minimum Node Cover in an Arbitrary Graph.
Descriptive Note : Research rept.,
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
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 nodeclique 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 nodeclique 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