Exact algorithms for problems related to the densest k-set problem
Exact algorithms for problems related to the densest k-set problem
复制标题
DOI：
10.1016/j.ipl.2014.04.009
复制
发表时间：
2014-09-01
影响因子：
0.5
通讯作者：
Wu, Guan-Han
中科院分区：
文献类型：
--
作者：
Chang, Maw-Shang;Chen, Li-Hsuan;Wu, Guan-Han
许多图的概念，如集团、k-Club和k-plex被用来定义社交网络中的内聚子群。最稠密k-集的概念就是其中之一。无向图G=(V，E)中的最稠密k-集是V的一个大小为k的顶点集S子集，使得S导出的子图的边数是由k个点集诱导的所有子图中的最大边数.通过穷举搜索技术可以在O(k(2)n(K))时间内得到G的一个最密集k-集.然而，当k的值接近n/2时，穷举搜索算法的运行时间为O*(2(N)).在n个顶点的无向图中，是否存在一个具有固定常数c<；2的O*(c(N))时间算法来寻找最密集的k-集，在文献中一直没有定论。本文指出最密集k-集合问题和一类与最密集k-集合概念有关的问题可以在O*(1.7315(N))时间内求解。(C)2014爱思唯尔B.V.保留所有权利。
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) is a vertex set S subset of 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 (k(2)n(k)) time by exhaustive-search technique for an undirected graph of n vertices and a number k < n. However, if the value of k approaches n/2, the running time of the exhaustive-search algorithm is O*(2(n)). Whether there exists an O*(c(n))-time algorithm with the fixed constant c < 2 to find a densest k-set in an undirected graph of n vertices remains open in the literature. In this paper, we point out that the densest k-set problem and a class of problems related to the concept of densest k-sets can be solved in time O*(1.7315(n)). (C) 2014 Elsevier B.V. All rights reserved.