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

Energy function-based approaches to graph coloring.

A Di Blas1, A Jagota, R Hughey

  • 1Dept. of Comput. Eng., California Univ., Santa Cruz, CA.

IEEE Transactions on Neural Networks
|February 5, 2008
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 a novel optimization method using a quasi-Hopfield network for graph coloring problems. The approach offers a more efficient and natural encoding, yielding competitive results against existing algorithms.

Area of Science:

  • Artificial Intelligence
  • Computational Complexity
  • Network Science

Background:

  • Optimization problems, such as graph coloring, are computationally challenging.
  • Previous applications of Hopfield networks to graph coloring had limitations in encoding efficiency and neuron type.
  • A need exists for more effective and compact neural network approaches for combinatorial optimization.

Purpose of the Study:

  • To present a novel optimization framework based on a multiple-restart quasi-Hopfield network.
  • To apply this framework to three distinct graph coloring problem variants.
  • To demonstrate the advantages of k-state neurons over binary neurons in this context.

Main Methods:

  • Developed a quasi-Hopfield network optimization approach.

Related Experiment Videos

  • Embedded problem-specific knowledge solely within the energy function.
  • Utilized k-state neurons for graph coloring, differing from prior binary neuron approaches.
  • Applied the method to minimum coloring, spanning subgraph k-coloring, and induced subgraph k-coloring problems.

    • Main Results:

    • The proposed k-state neuron encoding is more compact and natural than previous binary neuron methods.
    • The new approach significantly reduces network connections asymptotically.
    • It effectively avoids the issue of multiple colors assigned to a single vertex.
    • Experimental results show favorable comparisons with existing graph coloring algorithms, including non-neural methods.

    Conclusions:

    • The quasi-Hopfield network with k-state neurons provides an effective and efficient method for graph coloring optimization.
    • This approach offers a significant improvement over previous neural network applications in terms of encoding and problem handling.
    • The framework demonstrates strong performance, comparable to specialized algorithms.