The Minimum Feedback Arc Set Problem is NP-hard for Tournaments

Abstract : Answering a question of Bang-Jensen and Thomassen, we prove that the minimum feedback arc set problem is NP-hard for tournaments.
Type de document :
Article dans une revue
Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2007, 16, pp.01-04. 〈http://www.lirmm.fr/~thomasse/liste/feedback.pdf〉. 〈10.1017/S0963548306007887〉
Liste complète des métadonnées

Littérature citée [5 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00140321
Contributeur : Stephan Thomasse <>
Soumis le : samedi 14 avril 2007 - 10:02:59
Dernière modification le : jeudi 15 novembre 2018 - 20:26:55
Document(s) archivé(s) le : mardi 6 avril 2010 - 22:29:58

Fichier

Identifiants

Collections

Citation

Pierre Charbit, Stéphan Thomassé, Anders Yeo. The Minimum Feedback Arc Set Problem is NP-hard for Tournaments. Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2007, 16, pp.01-04. 〈http://www.lirmm.fr/~thomasse/liste/feedback.pdf〉. 〈10.1017/S0963548306007887〉. 〈lirmm-00140321〉

Partager

Métriques

Consultations de la notice

442

Téléchargements de fichiers

440