Weighted Coloring in Trees

Julio Araujo 1, 2 Nicolas Nisse 2 Stéphane Pérennes 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Nous prouvons que, en supposant qu'il n'existe aucun algorithme sous-exponentiel pour résoudre 3-SAT (ETH), alors le meilleur algorithme pour résoudre le probléme de coloration pondérée dans les arbres a une complexité de $n^{\Theta(\log n)}$, oú $n$ est la taille de l'entrée.
Type de document :
Rapport
[Research Report] RR-8249, INRIA. 2013
Liste complète des métadonnées


https://hal.inria.fr/hal-00794622
Contributeur : Nicolas Nisse <>
Soumis le : jeudi 7 mars 2013 - 13:02:51
Dernière modification le : vendredi 16 septembre 2016 - 15:19:08
Document(s) archivé(s) le : dimanche 2 avril 2017 - 10:05:14

Fichier

RR-8249.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00794622, version 2

Collections

Citation

Julio Araujo, Nicolas Nisse, Stéphane Pérennes. Weighted Coloring in Trees. [Research Report] RR-8249, INRIA. 2013. <hal-00794622v2>

Partager

Métriques

Consultations de
la notice

522

Téléchargements du document

160