Linear programming based approximation algorithms for feedback set problems in bipartite tournaments

DOI10.1016/J.TCS.2010.10.047MaRDI QIDQ534571zbMATH OpenOpenAlexFDO

Authors Anke van Zuylen

Publication date 18 May 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.10.047

zbMATH Keywords

linear programmingapproximation algorithmfeedback arc setfeedback vertex setbipartite tournament

Mathematics Subject Classification ID

Linear programming (90C05) Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments
• Feedback arc set problem in bipartite tournaments
• Feedback Arc Set Problem in Bipartite Tournaments
• An approximation algorithm for feedback vertex sets in tournaments
• A Min-Max Theorem on Feedback Vertex Sets

Cites work

• scientific article; zbMATH DE number 5485441 (Why is no real title available?)
• scientific article; zbMATH DE number 219267 (Why is no real title available?)
• A Min-Max Theorem on Feedback Vertex Sets
• Aggregating inconsistent information: ranking and clustering
• An approximation algorithm for feedback vertex sets in tournaments
• Approximating minimum feedback sets and multicuts in directed graphs
• Deterministic pivoting algorithms for constrained ranking and clustering problems
• Deterministic pivoting algorithms for constrained ranking and clustering problems
• Feedback arc set in bipartite tournaments is NP-complete
• Feedback arc set problem in bipartite tournaments
• Improved approximation algorithm for the feedback set problem in a bipartite tournament

Cited in

(13)

• A Min-Max Theorem on Feedback Vertex Sets
• Improved FPT algorithm for feedback vertex set problem in bipartite tournament
• A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
• Fixed-parameter tractability results for feedback set problems in tournaments
• Parameterized algorithms for feedback set problems and their duals in tournaments
• On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments
• Minimum feedback arc sets in rotator and incomplete rotator graphs
• Feedback vertex sets on restricted bipartite graphs
• Feedback arc set problem in bipartite tournaments
• Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments
• Feedback Arc Set Problem in Bipartite Tournaments
• Circular convex bipartite graphs: feedback vertex sets
• Vertex deletion on split graphs: beyond 4-hitting set

This page was built for publication: Linear programming based approximation algorithms for feedback set problems in bipartite tournaments

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