An Approximation Algorithm for Feedback Vertex Sets in Tournaments
From MaRDI portal
Publication:2719120
DOI10.1137/S0097539798338163zbMath0980.68053OpenAlexW2088180270MaRDI QIDQ2719120
Wenan Zang, Mao-cheng Cai, Xiaotie Deng
Publication date: 21 June 2001
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539798338163
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Improved FPT algorithm for feedback vertex set problem in bipartite tournament, Improved bounds for minimal feedback vertex sets in tournaments, Feedback vertex sets on restricted bipartite graphs, Improved approximation algorithms for hitting 3-vertex paths, A \(7 / 3\)-approximation algorithm for feedback vertex set in tournaments via Sherali-Adams, Packing cycles exactly in polynomial time, Packing cycles in graphs. II, Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs, A spin glass approach to the directed feedback vertex set problem, Two Hardness Results on Feedback Vertex Sets, Ranking tournaments with no errors. II: Minimax relation, Linear programming based approximation algorithms for feedback set problems in bipartite tournaments, Fixed-parameter tractability results for feedback set problems in tournaments, Fixed-parameter algorithms for cluster vertex deletion, Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms, Ranking tournaments with no errors. I: Structural description, A tight approximation algorithm for the cluster vertex deletion problem, On ideal semicomplete digraphs, Feedback arc number and feedback vertex number of Cartesian product of directed cycles, A tight approximation algorithm for the cluster vertex deletion problem, Tournaments and Semicomplete Digraphs
