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

DOI10.1016/j.tcs.2010.10.047zbMath1216.68344OpenAlexW2115051629MaRDI QIDQ534571

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 algorithmbipartite tournamentfeedback vertex setfeedback arc set

Mathematics Subject Classification ID

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

Related Items

Circular convex bipartite graphs: feedback vertex sets, A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments, Feedback vertex sets on restricted bipartite graphs, MINIMUM FEEDBACK ARC SETS IN ROTATOR AND INCOMPLETE ROTATOR GRAPHS, Vertex deletion on split graphs: beyond 4-hitting set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Feedback arc set in bipartite tournaments is NP-complete
• Improved approximation algorithm for the feedback set problem in a bipartite tournament
• Approximating minimum feedback sets and multicuts in directed graphs
• Feedback arc set problem in bipartite tournaments
• An Approximation Algorithm for Feedback Vertex Sets in Tournaments
• Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems
• A Min-Max Theorem on Feedback Vertex Sets
• Aggregating inconsistent information