Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00140321
Contributor : Stephan Thomasse <>
Submitted on : Saturday, April 14, 2007 - 10:02:59 AM
Last modification on : Saturday, March 28, 2020 - 2:24:14 AM
Long-term archiving on: : Tuesday, April 6, 2010 - 10:29:58 PM

Identifiers

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. ⟨10.1017/S0963548306007887⟩. ⟨lirmm-00140321⟩

Share

Metrics

Record views

746

Files downloads

860