Feedback arc set problem in bipartite tournaments

DOI10.1016/J.IPL.2007.08.023MaRDI QIDQ2380064zbMATH OpenOpenAlexFDO

Authors Sushmita Gupta

Publication date 24 March 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.08.023

zbMATH Keywords

approximation algorithmsbipartite tournamentsfeedback arc set

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Feedback Arc Set Problem in Bipartite Tournaments
• Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments
• Linear programming based approximation algorithms for feedback set problems in bipartite tournaments
• A quadratic vertex kernel for feedback arc set in bipartite tournaments
• An approximation algorithm for feedback vertex sets in tournaments

Cites work

• Aggregating inconsistent information
• Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems
• Feedback arc set in bipartite tournaments is NP-complete
• scientific article; zbMATH DE number 3972888 (Why is no real title available?)
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Ordering by weighted number of wins gives a good ranking for weighted tournaments
• Packing directed circuits fractionally
• Ranking Tournaments
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments

Cited in

(7)

• Fixed-parameter tractability results for feedback set problems in tournaments
• Sorting noisy data with partial information
• Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments
• A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
• Linear programming based approximation algorithms for feedback set problems in bipartite tournaments
• Feedback Arc Set Problem in Bipartite Tournaments
• Feedback arc set in bipartite tournaments is NP-complete

This page was built for publication: Feedback arc set problem in bipartite tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380064)