An approximation algorithm for feedback vertex sets in tournaments

DOI10.1137/S0097539798338163MaRDI QIDQ2719120zbMATH OpenOpenAlexFDO

Authors 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, http://hdl.handle.net/10722/42995

zbMATH Keywords

approximation algorithmfeedback vertex setmin-max relationtournament

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A 7/3-approximation for feedback vertex sets in tournaments
• A Min-Max Theorem on Tournaments
• A min-max theorem on feedback vertex sets. (Preliminary version)
• A Min-Max Theorem on Feedback Vertex Sets
• Feedback vertex sets in tournaments

Cited in

(36)

• Packing cycles in graphs. II
• Ranking tournaments with no errors. II: Minimax relation
• Fixed-parameter tractability results for feedback set problems in tournaments
• Ranking tournaments with no errors. I: Structural description
• On ideal semicomplete digraphs
• Feedback arc number and feedback vertex number of Cartesian product of directed cycles
• On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments
• Improved FPT algorithm for feedback vertex set problem in bipartite tournament
• Feedback arc set problem in bipartite tournaments
• Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms
• Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs
• Two Hardness Results on Feedback Vertex Sets
• Tournaments and Semicomplete Digraphs
• A spin glass approach to the directed feedback vertex set problem
• A Min-Max Theorem on Tournaments
• Feedback vertex sets in tournaments
• Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments
• Feedback vertex sets on restricted bipartite graphs
• Packing cycles exactly in polynomial time
• A min-max theorem on feedback vertex sets. (Preliminary version)
• Improved bounds for minimal feedback vertex sets in tournaments
• A 7/3-approximation for feedback vertex sets in tournaments
• Improved Bounds for Minimal Feedback Vertex Sets in Tournaments
• Feedback vertex sets in tournaments
• 2-Approximating Feedback Vertex Set in Tournaments
• 2-Approximating Feedback Vertex Set in Tournaments
• Linear programming based approximation algorithms for feedback set problems in bipartite tournaments
• Feedback Arc Set Problem in Bipartite Tournaments
• A Min-Max Theorem on Feedback Vertex Sets
• A tight approximation algorithm for the cluster vertex deletion problem
• A tight approximation algorithm for the cluster vertex deletion problem
• A 7 / 3-approximation algorithm for feedback vertex set in tournaments via Sherali-Adams
• Quick-sort style approximation algorithms for generalizations of feedback vertex set in tournaments
• A (2+)-factor approximation algorithm for split vertex deletion
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Fixed-parameter algorithms for cluster vertex deletion

This page was built for publication: An approximation algorithm for feedback vertex sets in tournaments

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