Carregant...
Carregant...

Vés al contingut (premeu Retorn)

A simple and fast heuristic algorithm for edge-coloring of graphs

Autor
Fiol, M.; Vilaltella Castanyer, Joan
Tipus d'activitat
Article en revista
Revista
AKCE international journal of graphs and combinatorics
Data de publicació
2013-10
Volum
10
Número
3
Pàgina inicial
263
Pàgina final
272
URL
http://www.scopus.com/record/display.url?eid=2-s2.0-84885152359&origin=inward Obrir en finestra nova
Resum
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 ¿ -regular graphs are presented, and a full implementation of the algorithm is given to facilitate its use...
Paraules clau
Conflicting vertex, Cubic graph, Edge-coloring, Heuristic algorithm, Regular graph, Snark
Grup de recerca
COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions

Participants