In this chapter we discuss a common derandomized approximation algorithm for yielding a constant-tunable approximation bound to two variants of the critical node detection problem. The goal of the respective problems is to reduce total pairwise connectivity or number of vertices to delete in order to achieve bounded component sizes in the residual graph, respectively. Our algorithms are built upon previous research and improved by an efficient local search algorithm that incorporates the closeness centrality. We show that the original approximation algorithm bounds remain in tact, while the practical performance is greatly improved. To highlight the results we utilize five common network data sets of various sizes.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 email@example.com
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 firstname.lastname@example.org