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 Access content directly
Reports (Research Report) Year : 2006

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

Dates and versions

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

Identifiers

  • HAL Id : lirmm-00121842 , version 1

Cite

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 View
96 Download

Share

Gmail Facebook X LinkedIn More