A 4-approximation for the line-column paths colouring problem in bi-directed meshes networks

Abstract : 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].
Type de document :
Rapport
[Research Report] RR-06060, LIRMM. 2006
Liste complète des métadonnées

Littérature citée [5 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00121842
Contributeur : Jérôme Palaysi <>
Soumis le : vendredi 22 décembre 2006 - 11:48:01
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : mercredi 7 avril 2010 - 01:15:38

Fichiers

Identifiants

  • HAL Id : lirmm-00121842, version 1

Collections

Citation

Jérôme Palaysi, Olivier Cogis, Guillaume Bagan. A 4-approximation for the line-column paths colouring problem in bi-directed meshes networks. [Research Report] RR-06060, LIRMM. 2006. 〈lirmm-00121842〉

Partager

Métriques

Consultations de la notice

188

Téléchargements de fichiers

102