Loading...
Please wait, while we are loading the content...
Similar Documents
Approximating the maximum weight clique using replicatot dynamics (2000)
| Content Provider | CiteSeerX |
|---|---|
| Author | Bomze, Immanuel M. Pelillo, Marcello Stix, Volker |
| Abstract | Abstract—Given an undirected graph with weights on the vertices, the maximum weight clique problem (MWCP) is to find a subset of mutually adjacent vertices (i.e., a clique) having the largest total weight. This is a generalization of the classical problem of finding the maximum cardinality clique of an unweighted graph, which arises as a special case of the MWCP when all the weights associated to the vertices are equal. The problem is known to be-hard for arbitrary graphs and, according to recent theoretical results, so is the problem of approximating it within a constant factor. Although there has recently been much interest around neural-network algorithms for the unweighted maximum clique problem, no effort has been directed so far toward its weighted counterpart. In this paper, we present a parallel, distributed heuristic for approximating the MWCP based on dynamics principles developed and studied in various |
| File Format | |
| Journal | IEEE Transaction. Neural Networks |
| Language | English |
| Publisher Date | 2000-01-01 |
| Access Restriction | Open |
| Subject Keyword | Replicatot Dynamic Maximum Weight Clique Dynamic Principle Recent Theoretical Result Undirected Graph Abstract Given Unweighted Maximum Clique Problem Neural-network Algorithm Classical Problem Constant Factor Arbitrary Graph Much Interest Weighted Counterpart Special Case Maximum Cardinality Clique Total Weight Maximum Weight Clique Problem Adjacent Vertex Unweighted Graph |
| Content Type | Text |
| Resource Type | Article |
