Linear programming based approximation algorithms for feedback set problems in bipartite tournaments
From MaRDI portal
Publication:534571
DOI10.1016/j.tcs.2010.10.047zbMath1216.68344OpenAlexW2115051629MaRDI QIDQ534571
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
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