Generalized minimum dominating set and application in automatic text summarization

Abstract

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.

arXiv comment11 pages, including 4 figures and 2 tables. To be published in Journal of Physics: Conference Series

References in corpus (12)

• LexRank: Graph-based Lexical Centrality as Salience in Text Summarization
• The Bethe lattice spin glass revisited
• Control Principles of Complex Networks
• Minimum Dominating Sets in Scale-Free Network Ensembles
• Network Observability Transitions
• Distance-d covering problems in scale-free networks with degree correlations
• Statistical Mechanics of the Minimum Dominating Set Problem
• Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results
• Statistical Mechanics of maximal independent sets
• Suppressing epidemics on networks by exploiting observer nodes
• The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
• Control principles of metabolic networks