Complexity of greedy edge-colouringReportar como inadecuado




Complexity of greedy edge-colouring - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués 2 UFC - Universidade Federal do Ceará 3 UFV - University of the Fraser Valley

Abstract : The Grundy index of a graph G = V, E is the greatest number of colours that the greedy edge-colouring algorithm can use on G. We prove that the problem of determining the Grundy index of a graph G = V, E is NP-hard for general graphs. We also show that this problem is polynomial-time solvable for caterpillars. More specifically, we prove that the Grundy index of a caterpillar is G or G + 1 and present a polynomial-time algorithm to determine it exactly.





Autor: Frédéric Havet - A Karolinna Maia - Min-Li Yu -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados