Generalized minimum dominating set and application in automatic text summarization
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Text SummarizationSimilar Papers 제목 키워드 기반
A Simulated Annealing-Based Multiobjective Optimization Algorithm for Minimum Weight Minimum Connected Dominating Set Problem
Minimum connected dominating set problem is an NP-hard combinatorial optimization problem in graph theory. Finding connected dominating set is of high interest in various domains such as wireless sensor networks, optical…
Combinatorial OptimizationMultiobjective OptimizationLocal Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function
The Minimum Weight Dominating Set (MWDS) problem is an important generalization of the Minimum Dominating Set (MDS) problem with extensive applications. This paper proposes a new local search algorithm for the MWDS probl…
An Efficient Matheuristic for the Minimum-Weight Dominating Set Problem
A minimum dominating set in a graph is a minimum set of vertices such that every vertex of the graph either belongs to it, or is adjacent to one vertex of this set. This mathematical object is of high relevance in a numb…
Learning-Based Heuristic for Combinatorial Optimization of the Minimum Dominating Set Problem using Graph Convolutional Networks
A dominating set of a graph $\mathcal{G=(V, E)}$ is a subset of vertices $S\subseteq\mathcal{V}$ such that every vertex $v\in \mathcal{V} \setminus S$ outside the dominating set is adjacent to a vertex $u\in S$ within th…
Combinatorial OptimizationEvolution is Still Good: Theoretical Analysis of Evolutionary Algorithms on General Cover Problems
Theoretical studies on evolutionary algorithms have developed vigorously in recent years. Many such algorithms have theoretical guarantees in both running time and approximation ratio. Some approximation mechanism seems …
Evolutionary Algorithms