Comparisons of Energy-Descent Optimization Algorithms for Maximum Clique Problems (Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
A clique of a graph G (V,E) is a subset of V such that every pair of vertices is connected by an edge in E. Finding a maximum clique of an arbitrary graph is a well-known NP-complete problem. Recently, several polynomial time "energy-descent optimization" algorithms have been proposed for approximating the maximum clique problem, where they seek a solution by minimizing the energy function representing the constraints and the goal function. In this paper, we propose the binary neural network as an efficient synchronous energy-descent optimization algorithm. Through two types of random graphs, we compare the performance of four promising energy-descent optimization algorithms. The simulation results show that "RaCLIQUE," the modified Boltzmann machine algorithm, is the best asynchronous algorithm for random graphs, while the binary neural network is the best one for k random cliques graphs.
- 社団法人電子情報通信学会の論文
- 1996-04-25
著者
-
Funabiki N
Graduate School Of Natural Science And Technology Okayama University
-
Funabiki Nobuo
Faculty Of Engineering Science Osaka University
-
NISHIKAWA Seishi
the Department of Information and Computer Sciences, School of Engineering Science, Osaka University
-
NISHIKAWA Seishi
Faculty of Engineering Science, Osaka University
-
Nishikawa S
The Department Of Information And Computer Sciences School Of Engineering Science Osaka University
-
Nishikawa Seishi
Faculty Of Engineering Science Osaka University
関連論文
- A WDS Clustering Algorithm for Wireless Mesh Networks
- An Optical-Drop Wavelength Assignment Algorithm for Efficient Wavelength Reuse under Heterogeneous Traffic in WDM Ring Networks(Discrete Mathematics and Its Applications)
- A Minimum Dead Space Algorithm for Generalized Isochronous Channel Reuse Problems in DQDB Networks(Network)
- P2PMM_router : A Two-Stage Heuristic Algorithm to Peer-to-Peer Multicast Routing Problems in Multihome Networks(Discrete Mathematics and Its Applications)
- A Quasi-Solution State Evolution Algorithm for Channel Assignment Problems in Cellular Networks(Special Section on Discrete Mathematics and Its Applications)
- A Proposal of Optimal Path Selection Algorithm for Static and Mobile Multicast Routing Problems
- Relaxation of Coefficient Sensitiveness to Performance for Neural Networks Using Neuron Filter through Total Coloring Problems
- A Proposal of Neuron Filter: A Constraint Resolution Scheme of Neural Networks for Combinatorial Optimization Problems
- A Digital Neural Network for Multilayer Channel Routing with Crosstalk Minimization
- A Massive Digital Neural Network for Total Coloring Problems
- A Gradual Neural Network Approach for Time Slot Assignment in TDM Multicast Switching Systems
- Comparisons of Energy-Descent Optimization Algorithms for Maximum Clique Problems (Special Section on Discrete Mathematics and Its Applications)
- A Binary Neural Network Approach for Link Activation Problems in Multihop Radio Networks
- An Improved Neural Network for Channel Assignment Problems in Cellular Mobile Communication Systems