An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm
From MaRDI portal
Publication:2176284
Abstract: We study the behavior of the Douglas-Rachford algorithm on the graph vertex-coloring problem. Given a graph and a number of colors, the goal is to find a coloring of the vertices so that all adjacent vertex pairs have different colors. In spite of the combinatorial nature of this problem, the Douglas-Rachford algorithm was recently shown to be a successful heuristic for solving a wide variety of graph coloring instances, when the problem was cast as a feasibility problem on binary indicator variables. In this work we consider a different formulation, based on semidefinite programming. The much improved performance of the Douglas-Rachford algorithm, with this new approach, is demonstrated through various numerical experiments.
Recommendations
- The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
- Recent results on Douglas-Rachford methods.
- Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem
- Fractional programming formulation for the vertex coloring problem
- New algorithm for calculating chromatic index of graphs and its applications
Cites work
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- scientific article; zbMATH DE number 3671159 (Why is no real title available?)
- scientific article; zbMATH DE number 1380613 (Why is no real title available?)
- scientific article; zbMATH DE number 821271 (Why is no real title available?)
- scientific article; zbMATH DE number 6125590 (Why is no real title available?)
- A graph coloring algorithm for large scheduling problems
- A guide to graph colouring. Algorithms and applications
- A survey of graph coloring -- its types, methods and applications
- Almost all graphs with 2. 522\(n\) edges are not 3-colorable
- An application of graph coloring to printed circuit testing
- Applications of convex analysis within mathematics
- Approximate graph coloring by semidefinite programming
- Benchmarking optimization software with performance profiles.
- Convex analysis and monotone operator theory in Hilbert spaces
- Decomposition through formalization in a product space
- Douglas-Rachford feasibility methods for matrix completion problems
- Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem
- Globalizing stabilized sequential quadratic programming method by smooth primal-dual exact penalty function
- Iterative methods for fixed point problems in Hilbert spaces
- Linear convergence of the Douglas-Rachford method for two closed sets
- Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
- On the local convergence of the Douglas-Rachford algorithm
- Projection methods: Swiss army knives for solving feasibility and best approximation problems with halfspaces
- Recent results on Douglas-Rachford methods for combinatorial optimization problems
- Reducibility among combinatorial problems
- Regularity properties of non-negative sparsity sets
- Searching with iterated maps
- Solving graph coloring problems with the Douglas-Rachford algorithm
- The Douglas-Rachford algorithm for the case of the sphere and the line
Cited in
(8)- Douglas–Rachford algorithm for control-constrained minimum-energy control problems
- Non-separable multidimensional multiresolution wavelets: a Douglas-Rachford approach
- SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
- Circumcentering reflection methods for nonconvex feasibility problems
- Solving graph coloring problems with the Douglas-Rachford algorithm
- General splitting methods with linearization for the split feasibility problem
- An incremental search heuristic for coloring vertices of a graph
- The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
This page was built for publication: An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2176284)
