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

PIERRE CHARBIT; STÉPHAN THOMASSÉ; ANDERS YEO

doi:10.1017/S0963548306007887

Dom, Michael Guo, Jiong Hüffner, Falk Niedermeier, Rolf and Truß, Anke 2006. Algorithms and Complexity. Vol. 3998, Issue. , p. 320.

Ailon, Nir and Alon, Noga 2007. Hardness of fully dense problems. Information and Computation, Vol. 205, Issue. 8, p. 1117.

Guo, Jiong Hüffner, Falk and Moser, Hannes 2007. Feedback arc set in bipartite tournaments is NP-complete. Information Processing Letters, Vol. 102, Issue. 2-3, p. 62.

Charon, Irène and Hudry, Olivier 2007. A survey on the linear ordering problem for weighted or unweighted tournaments. 4OR, Vol. 5, Issue. 1, p. 5.

Brandt, Felix and Fischer, Felix 2008. Computing the minimal covering set. Mathematical Social Sciences, Vol. 56, Issue. 2, p. 254.

Gupta, Sushmita 2008. Feedback arc set problem in bipartite tournaments. Information Processing Letters, Vol. 105, Issue. 4, p. 150.

Hudry, Olivier 2008. NP-hardness results for the aggregation of linear orders into median orders. Annals of Operations Research, Vol. 163, Issue. 1, p. 63.

Coleman, Tom and Wirth, Anthony 2009. Ranking tournaments. ACM Journal of Experimental Algorithmics, Vol. 14, Issue. ,

Bang-Jensen, Jørgen 2009. Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs. Discrete Mathematics, Vol. 309, Issue. 18, p. 5655.

Hudry, Olivier 2009. A survey on the complexity of tournament solutions. Mathematical Social Sciences, Vol. 57, Issue. 3, p. 292.

Hudry, Olivier 2009. Encyclopedia of Complexity and Systems Science. p. 9942.

VAN IERSEL, LEO KELK, STEVEN and MNICH, MATTHIAS 2009. UNIQUENESS, INTRACTABILITY AND EXACT ALGORITHMS: REFLECTIONS ON LEVEL-K PHYLOGENETIC NETWORKS. Journal of Bioinformatics and Computational Biology, Vol. 07, Issue. 04, p. 597.

van Zuylen, Anke and Williamson, David P. 2009. Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems. Mathematics of Operations Research, Vol. 34, Issue. 3, p. 594.

Hudry, Olivier Leclerc, Bruno Monjardet, Bernard and Barthélemy, Jean‐Pierre 2009. Decision‐making Process. p. 811.

Roemer, Thomas and Ahmadi, Reza 2009. Models for Concurrent Product and Process Design. SSRN Electronic Journal,

Roemer, Thomas A. and Ahmadi, Reza 2010. Models for concurrent product and process design. European Journal of Operational Research, Vol. 203, Issue. 3, p. 601.

Karpinski, Marek and Schudy, Warren 2010. Algorithms and Computation. Vol. 6506, Issue. , p. 3.

Hudry, Olivier 2010. On the complexity of Slater’s problems. European Journal of Operational Research, Vol. 203, Issue. 1, p. 216.

Charon, Irène and Hudry, Olivier 2010. An updated survey on the linear ordering problem for weighted or unweighted tournaments. Annals of Operations Research, Vol. 175, Issue. 1, p. 107.

Dom, Michael Guo, Jiong Hüffner, Falk Niedermeier, Rolf and Truss, Anke 2010. Fixed-parameter tractability results for feedback set problems in tournaments. Journal of Discrete Algorithms, Vol. 8, Issue. 1, p. 76.

Article contents

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

Abstract

Access options

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Article contents

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

Abstract

Access options

Save article to Kindle

Save article to Dropbox

Save article to Google Drive

Reply to: Submit a response

Your details

You have entered the maximum number of contributors

Conflicting interests