INFORMS journal on computing · 2014 · 60 citations · 25 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsSet TheoryCombinatorial OptimizationGraph AlgorithmsGraph TheoryBenders DecompositionBranch-and-cutDominating SetsExact AlgorithmsGraph DecompositionsHybrid Algorithms
We present exact algorithms for solving the minimum connected dominating set problem in an undirected graph. The algorithms are based on two approaches: a Benders decomposition algorithm and a branch-and-cut method. We also develop a hybrid algorithm that combines these two approaches. Two variants of each of the three resulting algorithms are considered: a stand-alone version and an iterative probing variant. The latter variant is based on a simple property of the problem, which states that if no connected dominating set of a given cardinality exists, then there are no connected dominating sets of lower cardinality. We present computational results on a large set of instances from the literature.
25
Mining the network value of customers
Pedro Domingos, Matt Richardson · 2001 · 2.9K citations
Modelling disease outbreaks in realistic urban social networks
Stephen Eubank, Hasan Güçlü, V. S. Anil Kumar et al. · Nature · 2004 · 2.2K citations · Full text
Veterinary Medicine, Infectious Diseases, Urban Planning +14
Approximation Algorithms for Connected Dominating Sets
Suvajyoti Guha, Samir Khuller · Algorithmica · 1998 · 1.1K citations
Dominic Welsh · Bulletin of the London Mathematical Society · 1974 · 1.1K citations