A probabilistic estimator for the vertex
โ
C.A. Mandal; P.P. Chakrabarti; S. Ghose
๐
Article
๐
1998
๐
Elsevier Science
๐
English
โ 264 KB
Vertex deletion is a well-known NP-complete problem. An empirical method for estimating the number of vertices that need to be deleted to make a graph bipartite is presented. The estimator has been developed by modelling the problem using random graphs where an edge is present with a fixed probabili