A PROBABILISTIC ESTIMATOR FOR THE VERTEX DELETION PROBLEM

Authors
MANDAL CA CHAKRABARTI PP GHOSE S
Citation
Ca. Mandal et al., A PROBABILISTIC ESTIMATOR FOR THE VERTEX DELETION PROBLEM, Computers & mathematics with applications, 35(6), 1998, pp. 1-4
Citations number
4
Categorie Soggetti
Mathematics,"Computer Science Interdisciplinary Applications",Mathematics,"Computer Science Interdisciplinary Applications
Journal title
Computers & mathematics with applications → ACNP
ISSN journal
08981221
Volume
35
Issue
6
Year of publication
1998
Pages
1 - 4
Database
ISI
SICI code
0898-1221(1998)35:6<1:APEFTV>2.0.ZU;2-I
Abstract
Vertex deletion is a well-known NP-complete problem. An empirical meth od for estimating the number of vertices that need to be deleted to ma ke a graph bipartite is presented. The estimator has been developed by modelling the problem using random graphs where an edge is present wi th a fixed probability p. The method works in O(n(2)) time, where n is the number of vertices in the graph. The estimator has been experimen ted on several randomly generated graphs. The results indicate that th e estimator gives accurate results for graphs of various sizes.