A 4-approximation for the line-column paths colouring problem in bi-directed meshes networks
Résumé
We study the row-column chain coloring problem in directed meshes (each directed chain is of one out of eight possible types). The decision problem is known to be NP-complete, and an 8-approximation algorithm has been provided for the associated optimization problem [KT03]. We improve on this result by providing a 4-approximation algorithm, thus catching up with the best non directed result known to us [BCP06].
Loading...