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.

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.

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.

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.

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

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

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

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

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

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.

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.

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.

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

Östergård, Patric R.J. and Vaskelainen, Vesa P. 2010. A tournament of order 14 with disjoint Banks and Slater sets. Discrete Applied Mathematics, Vol. 158, Issue. 5, p. 588.

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.

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.

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.

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

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