The Minimum Feedback Arc Set Problem is NP-hard for Tournaments - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Combinatorics, Probability and Computing Année : 2007

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

Pierre Charbit
Laboratoire d'informatique Algorithmique : Fondements et Applications
CV
Stéphan Thomassé
Algorithmes, Graphes et Combinatoire
Anders Yeo
  • Fonction : Auteur
Department of Computer Science

Résumé

Answering a question of Bang-Jensen and Thomassen, we prove that the minimum feedback arc set problem is NP-hard for tournaments.

Domaines

Complexité [cs.CC] Mathématique discrète [cs.DM]
Fichier principal
Vignette du fichier
feedback.pdf (129.19 Ko) Télécharger le fichier

Stephan Thomasse  : Connectez-vous pour contacter le contributeur

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00140321

Soumis le : samedi 14 avril 2007-10:02:59

Dernière modification le : vendredi 24 mars 2023-14:52:48

Archivage à long terme le : mardi 6 avril 2010-22:29:58

Télécharger pour visualiser

Dates et versions

lirmm-00140321 , version 1 (14-04-2007)

Identifiants

Citer

Pierre Charbit, Stéphan Thomassé, Anders Yeo. The Minimum Feedback Arc Set Problem is NP-hard for Tournaments. Combinatorics, Probability and Computing, 2007, 16, pp.01-04. ⟨10.1017/S0963548306007887⟩. ⟨lirmm-00140321⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

UNIV-PARIS7 CNRS LIAFA ALGCO LIRMM TDS-MACS MIPS UNIV-MONTPELLIER
359 Consultations
936 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More