𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the max coloring problem

✍ Scribed by Epstein, Leah; Levin, Asaf

Book ID
119375387
Publisher
Elsevier Science
Year
2012
Tongue
English
Weight
380 KB
Volume
462
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the max-weight edge coloring problem
On the max-weight edge coloring problem
✍ Giorgio Lucarelli; Ioannis Milis; Vangelis T. Paschos πŸ“‚ Article πŸ“… 2009 πŸ› Springer US 🌐 English βš– 416 KB
Approximating the max-edge-coloring prob
Approximating the max-edge-coloring problem
✍ N. Bourgeois; G. Lucarelli; I. Milis; V.Th. Paschos πŸ“‚ Article πŸ“… 2010 πŸ› Elsevier Science 🌐 English βš– 495 KB
On a hypercube coloring problem
On a hypercube coloring problem
✍ Patric R.J. Γ–stergΓ…rd πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 167 KB
The road coloring problem
The road coloring problem
✍ A. N. Trahtman πŸ“‚ Article πŸ“… 2009 πŸ› The Hebrew University Magnes Press 🌐 English βš– 123 KB
The permutation-path coloring problem on
The permutation-path coloring problem on trees
✍ Sylvie Corteel; Mario Valencia-Pabon; DaniΓ¨le Gardy; Dominique Barth; Alain Deni πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 292 KB

In this paper we ΓΏrst show that the permutation-path coloring problem is NP-hard even for very restrictive instances like involutions, which are permutations that contain only cycles of length at most two, on both binary trees and on trees having only two vertices with degree greater than two, and f