Skip to Main content Skip to Navigation
Reports

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].
Complete list of metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00121842
Contributor : Jérôme Palaysi <>
Submitted on : Friday, December 22, 2006 - 11:48:01 AM
Last modification on : Thursday, May 24, 2018 - 3:59:21 PM
Long-term archiving on: : Wednesday, April 7, 2010 - 1:15:38 AM

Files

Identifiers

  • 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⟩

Share

Metrics

Record views

243

Files downloads

190