A SIMPLE AND FAST HEURISTIC ALGORITHM FOR EDGE-COLORING OF GRAPHS

被引：0

作者：

Fiol, M. A. ^{[1
]}

Vilaltella, J. ^{[1
]}

机构：

[1] Univ Politecn Cataluna, Dept Matemat Aplicada 4, BarcelonaTech, Barcelona, Catalonia, Spain

来源：

AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS | 2013年 / 10卷 / 03期

关键词：

cubic graph; regular graph; edge-coloring; snark; conflicting vertex; heuristic algorithm;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A simple but empirically efficient heuristic algorithm for the edge-coloring of graphs is presented. Its basic idea is the displacement of 'conflicts' (repeated colors in the edges incident to a vertex) along paths of adjacent vertices whose incident edges are recolored by swapping alternating colors (that is, doing a Kempe interchange). The results of performance tests on random cubic and Delta-regular graphs are presented, and a full implementation of the algorithm is given to facilitate its use and the reproducibility of results.

引用

页码：263 / 272

页数：10

共 8 条

[1]

Biggs N., 1978, ANN NY ACAD SCI, V319, P71, DOI 10.1111/j.1749-6632.1979.tb32775.x

[2]

Fiol M.A., 1991, GRAPH THEORY COMBINA, V1, P493

[3]

Fiorini S., 1977, EDGE COLOURING GRAPH

[4] CATALAN NUMBERS - INTEGER SEQUENCE THAT MATERIALIZES IN UNEXPECTED PLACES [J].

GARDNER, M .

SCIENTIFIC AMERICAN, 1976, 234 (06) :120-&

[5] THE NP-COMPLETENESS OF EDGE-COLORING [J].

HOLYER, I .

SIAM JOURNAL ON COMPUTING, 1981, 10 (04) :718-720

[6] INFINITE FAMILIES OF NONTRIVIAL TRIVALENT GRAPHS WHICH ARE NOT TAIT COLORABLE [J].

ISAACS, R .

AMERICAN MATHEMATICAL MONTHLY, 1975, 82 (03) :221-239

[7]

Lee T. T., 2011, ARXIV11041852V1C

[8] ALMOST-ALL REGULAR GRAPHS ARE HAMILTONIAN [J].

ROBINSON, RW ;

WORMALD, NC .

RANDOM STRUCTURES & ALGORITHMS, 1994, 5 (02) :363-374

← 1 →