F. Odeh, I. Tadjbakhsh
Archive for Rational Mechanics and Analysis
We present an algorithm which finds a minimum vertex cover in a graph G(V, E) in time O(|V|+( a k)2 k 3), where for connected graphs G the parameter a is defined as the minimum number of edges that must be added to a tree to produce G, and k is the maximum a over all biconnected components of the graph. The algorithm combines two main approaches for coping with NP-completeness, and thereby achieves better running time than algorithms using only one of these approaches. © 1985.
F. Odeh, I. Tadjbakhsh
Archive for Rational Mechanics and Analysis
Shu Tezuka
WSC 1991
Harpreet S. Sawhney
IS&T/SPIE Electronic Imaging 1994
Matthew A Grayson
Journal of Complexity