Generalized minimum dominating set and application in automatic text summarization
This work addresses a graph theory problem with potential applications in text summarization, but it appears incremental as it builds on existing methods.
The authors tackled the generalized minimum dominating set problem using a replica-symmetric spin glass theory and derived belief-propagation equations, applying it to automatic text summarization with a preliminary test.
For a graph formed by vertices and weighted edges, a generalized minimum dominating set (MDS) is a vertex set of smallest cardinality such that the summed weight of edges from each outside vertex to vertices in this set is equal to or larger than certain threshold value. This generalized MDS problem reduces to the conventional MDS problem in the limiting case of all the edge weights being equal to the threshold value. We treat the generalized MDS problem in the present paper by a replica-symmetric spin glass theory and derive a set of belief-propagation equations. As a practical application we consider the problem of extracting a set of sentences that best summarize a given input text document. We carry out a preliminary test of the statistical physics-inspired method to this automatic text summarization problem.