Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Approximating maximum clique with a Hopfield network.

A Jagota1

  • 1Dept. of Math. Sci., Memphis State Univ., TN.

IEEE Transactions on Neural Networks
|January 1, 1995
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Surface tension, surface energy, and chemical potential due to their difference.

Langmuir : the ACS journal of surfaces and colloids·2013
Same author

[Implementation of the German Guideline for the Prevention, Diagnosis, Treatment, and Follow-up of Lung Cancer in the Federal State of Berlin].

Pneumologie (Stuttgart, Germany)·2012
Same author

First evaluation of the Joint Clinical Registries of the Coordinating Tumor Center of Berlin.

Anticancer research·2011
Same author

[Introduction of interdisciplinary prostate cancer centers based on the recommendations of the German Cancer Society. A cost-benefit analysis 3 years after accreditation].

Der Urologe. Ausg. A·2011
Same author

Thyroxine-induced alterations in the testis and seminal vesicles of air-breathing catfish, Clarias gariepinus.

Fish physiology and biochemistry·2009
Same author

Deposition and meniscus alignment of DNA-CNT on a substrate.

Journal of colloid and interface science·2008
Same journal

Universal perceptron and DNA-like learning algorithm for binary neural networks: LSBF and PBF implementations.

IEEE transactions on neural networks·2013
Same journal

Guest editorial: special section on white box nonlinear prediction models.

IEEE transactions on neural networks·2011
Same journal

Data-based fault-tolerant control of high-speed trains with traction/braking notch nonlinearities and actuator failures.

IEEE transactions on neural networks·2011
Same journal

Guest editorial: special section on data-based control, modeling, and optimization.

IEEE transactions on neural networks·2011
Same journal

Neural network-based multiple robot simultaneous localization and mapping.

IEEE transactions on neural networks·2011
Same journal

Data-driven model-free adaptive control for a class of MIMO nonlinear discrete-time systems.

IEEE transactions on neural networks·2011
See all related articles

This study introduces novel Hopfield network dynamics for efficiently approximating the MAX-CLIQUE problem. Mean-field annealing and stochastic dynamics demonstrate superior performance over naive heuristics on various graph types.

Area of Science:

  • Graph theory
  • Computational complexity
  • Artificial neural networks

Background:

  • The MAX-CLIQUE problem, finding the largest clique in a graph, is NP-hard.
  • Real-world problems often map to MAX-CLIQUE, necessitating efficient approximation algorithms.
  • Hopfield networks offer a framework for optimization problems.

Purpose of the Study:

  • To develop and evaluate energy-descent dynamics on a specialized Hopfield network for MAX-CLIQUE approximation.
  • To compare the performance of discrete and continuous dynamics against established heuristics.
  • To identify the most effective approximation strategies for MAX-CLIQUE.

Main Methods:

  • Utilized a Hopfield network model where stable states correspond to maximal cliques.
  • Implemented and tested discrete (deterministic, stochastic) and continuous energy-descent dynamics.

Related Experiment Videos

  • Conducted empirical comparisons on random and challenging graph instances.
  • Emulated existing greedy algorithms as special cases within the proposed dynamics.

    • Main Results:

    • Mean-field annealing and a specific stochastic dynamics emerged as the top-performing methods.
    • The proposed dynamics significantly outperformed approximations based on a naive greedy heuristic.
    • The Hopfield network approach provided efficient MAX-CLIQUE approximations.

    Conclusions:

    • Specialized Hopfield networks can effectively approximate the MAX-CLIQUE problem.
    • Mean-field annealing and stochastic dynamics offer a promising avenue for MAX-CLIQUE approximation.
    • The developed dynamics provide a substantial improvement over simpler greedy methods.