کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428532 | 686795 | 2014 | 4 صفحه PDF | دانلود رایگان |
• An O⁎(1.7315n)O⁎(1.7315n)-time exact algorithm for the densest k-set problem is proposed.
• The algorithm can be applied to solve a series of problems related to the densest k-set problem.
• All these related problems can also be solved in time O⁎(1.7315n)O⁎(1.7315n).
Many graph concepts such as cliques, k-clubs, and k-plexes are used to define cohesive subgroups in a social network. The concept of densest k-set is one of them. A densest k-set in an undirected graph G=(V,E)G=(V,E) is a vertex set S⊆VS⊆V of size k such that the number of edges in the subgraph of G induced by S is maximum among all subgraphs of G induced by vertex sets of size k. One can obtain a densest k-set of G in O(k2nk)O(k2nk) time by exhaustive-search technique for an undirected graph of n vertices and a number k
Journal: Information Processing Letters - Volume 114, Issue 9, September 2014, Pages 510–513