Solving Graph Coloring Problems with the Douglas-Rachford Algorithm

被引：10

作者：

Aragon Artacho, Francisco J. ^{[1
]}

Campoy, Ruben ^{[1
]}

机构：

[1] Univ Alicante, Alicante, Spain

来源：

SET-VALUED AND VARIATIONAL ANALYSIS | 2018年 / 26卷 / 02期

关键词：

Douglas-Rachford algorithm; Graph coloring; Feasibility problem; Non-convex; CONVERGENCE; FEASIBILITY; SETS;

D O I：

10.1007/s11228-017-0461-4

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We present the Douglas-Rachford algorithm as a successful heuristic for solving graph coloring problems. Given a set of colors, these types of problems consist in assigning a color to each node of a graph, in such a way that every pair of adjacent nodes are assigned with different colors. We formulate the graph coloring problem as an appropriate feasibility problem that can be effectively solved by the Douglas-Rachford algorithm, despite the nonconvexity arising from the combinatorial nature of the problem. Different modifications of the graph coloring problem and applications are also presented. The good performance of the method is shown in various computational experiments.

引用

页码：277 / 304

页数：28

共 34 条

[11] Finding best approximation pairs relative to two closed convex sets in Hilbert spaces [J].