The Minimum Feedback Arc Set Problem is NP-hard for Tournaments - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Combinatorics, Probability and Computing Year : 2007

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.

Domains

Computational Complexity [cs.CC] Discrete Mathematics [cs.DM]
Fichier principal
Vignette du fichier
feedback.pdf (129.19 Ko) Télécharger le fichier

Stephan Thomasse  : Connect in order to contact the contributor

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

Submitted on : Saturday, April 14, 2007-10:02:59 AM

Last modification on : Friday, March 24, 2023-2:52:48 PM

Long-term archiving on : Tuesday, April 6, 2010-10:29:58 PM

Download

Dates and versions

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

Identifiers

Cite

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⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

UNIV-PARIS7 CNRS LIAFA ALGCO LIRMM TDS-MACS MIPS UNIV-MONTPELLIER
378 View
1032 Download

Altmetric

Share

More