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.

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.

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

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.

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.

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,

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.

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

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

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 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.

Ö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.

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.

Bui-Xuan, Binh-Minh Telle, Jan Arne and Vatshelle, Martin 2010. H-join decomposable graphs and algorithms with runtime single exponential in rankwidth. Discrete Applied Mathematics, Vol. 158, Issue. 7, p. 809.

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.

Coppersmith, Don Fleischer, Lisa K. and Rurda, Atri 2010. Ordering by weighted number of wins gives a good ranking for weighted tournaments. ACM Transactions on Algorithms, Vol. 6, Issue. 3, p. 1.

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