Collective dynamics of phase-repulsive oscillators solves graph coloring problem
From MaRDI portal
Publication:5112986
Coloring of graphs and hypergraphs (05C15) Boundary value problems on graphs and networks for ordinary differential equations (34B45) Nonlinear oscillations and coupled oscillators for ordinary differential equations (34C15) Qualitative investigation and simulation of ordinary differential equation models (34C60) Combinatorial optimization (90C27)
Abstract: We show how to couple phase-oscillators on a graph so that collective dynamics "searches" for the coloring of that graph as it relaxes toward the dynamical equilibrium. This translates a combinatorial optimization problem (graph coloring) into a functional optimization problem (finding and evaluating the global minimum of dynamical non-equilibrium potential, done by the natural system's evolution). Using a sample of graphs, we show that our method can serve as a viable alternative to the traditional combinatorial algorithms. Moreover, we show that, with the same computational cost, our method efficiently solves the harder problem of improper coloring of weighed graphs.
Recommendations
- scientific article; zbMATH DE number 5989958
- Clustering dynamics of nonlinear oscillator network: Application to graph coloring problem
- k-phase oscillator synchronization for graph coloring
- A new oscillator coupling function for improving the solution of graph coloring problem
- Dynamical Hysteresis Neural Networks for Graph Coloring Problem
Cites work
- A First Course in Optimization Theory
- A guide to graph colouring. Algorithms and applications
- A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
- A survey on vertex coloring problems
- Chimera patterns in networks. Interplay between dynamics, structure, noise, and delay
- Circular colorings of edge-weighted graphs
- Clustering dynamics of nonlinear oscillator network: Application to graph coloring problem
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Dynamical systems on networks. A tutorial
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- scientific article; zbMATH DE number 1953201 (Why is no real title available?)
- scientific article; zbMATH DE number 5936982 (Why is no real title available?)
- List Improper Colourings of Planar Graphs
- Modelling mean fields in networks of coupled oscillators
- Models and solution techniques for frequency assignment problems
- New heuristics for the vertex coloring problem based on semidefinite programming
- New integer linear programming models for the vertex coloring problem
- Small Maximal Independent Sets and Faster Exact Graph Coloring
- Synchronization patterns in geometrically frustrated rings of relaxation oscillators
- The Kuramoto model in complex networks
- The Operator \Psi for the Chromatic Number of a Graph
- The role of asymmetrical and repulsive coupling in the dynamics of two coupled van der Pol oscillators
- The sandwich theorem
Cited in
(6)- A new oscillator coupling function for improving the solution of graph coloring problem
- OIM: oscillator-based Ising machines for solving combinatorial optimisation problems
- scientific article; zbMATH DE number 5989958 (Why is no real title available?)
- Dynamical Hysteresis Neural Networks for Graph Coloring Problem
- k-phase oscillator synchronization for graph coloring
- Clustering dynamics of nonlinear oscillator network: Application to graph coloring problem
This page was built for publication: Collective dynamics of phase-repulsive oscillators solves graph coloring problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5112986)
