排序方式: 共有2条查询结果,搜索用时 15 毫秒
1
1.
Balabhaskar?BalasundaramEmail author Sergiy?Butenko Svyatoslav?Trukhanov 《Journal of Combinatorial Optimization》2005,10(1):23-39
This paper proposes clique relaxations to identify clusters in biological networks. In particular, the maximum n-clique and maximum n-club problems on an arbitrary graph are introduced and their recognition versions are shown to be NP-complete. In addition, integer programming formulations are proposed and the results of sample numerical experiments performed on biological networks are reported. 相似文献
2.
Zhuqi Miao Balabhaskar Balasundaram Eduardo L. Pasiliao 《Journal of Combinatorial Optimization》2014,28(1):105-120
The maximum clique problem is a classical problem in combinatorial optimization that has a broad range of applications in graph-based data mining, social and biological network analysis and a variety of other fields. This article investigates the problem when the edges fail independently with known probabilities. This leads to the maximum probabilistic clique problem, which is to find a subset of vertices of maximum cardinality that forms a clique with probability at least \(\theta \in [0,1]\) , which is a user-specified probability threshold. We show that the probabilistic clique property is hereditary and extend a well-known exact combinatorial algorithm for the maximum clique problem to a sampling-free exact algorithm for the maximum probabilistic clique problem. The performance of the algorithm is benchmarked on a test-bed of DIMACS clique instances and on a randomly generated test-bed. 相似文献
1