Martin Charles Golumbic, Renu C. Laskar
Discrete Applied Mathematics
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.
Martin Charles Golumbic, Renu C. Laskar
Discrete Applied Mathematics
Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
Daniel J. Costello Jr., Pierre R. Chevillat, et al.
ISIT 1997
Ehud Altman, Kenneth R. Brown, et al.
PRX Quantum