The Minimum Feedback Arc Set Problem is NP-hard for Tournaments - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
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.
Fichier principal
Vignette du fichier
feedback.pdf (129.19 Ko) Télécharger le fichier
Loading...

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⟩
359 View
936 Download

Altmetric

Share

Gmail Facebook X LinkedIn More