A 4-approximation for the line-column paths colouring problem in bi-directed meshes networks - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2006

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].
Fichier principal
Vignette du fichier
BCP06.pdf (170.33 Ko) Télécharger le fichier
Loading...

Dates et versions

lirmm-00121842 , version 1 (22-12-2006)

Identifiants

  • HAL Id : lirmm-00121842 , version 1

Citer

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⟩
118 Consultations
96 Téléchargements

Partager

Gmail Facebook X LinkedIn More