Improved approximation algorithm for the feedback set problem in a bipartite tournament

DOI10.1016/j.orl.2007.12.005zbMath1210.90168OpenAlexW2020044991MaRDI QIDQ957363

Prashant Sasatte

Publication date: 27 November 2008

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2007.12.005

zbMATH Keywords

approximation algorithmbipartite tournamentfeedback set problemiterative roundinge

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Feedback vertex sets on restricted bipartite graphs, Two Hardness Results on Feedback Vertex Sets, Linear programming based approximation algorithms for feedback set problems in bipartite tournaments, Fixed-parameter tractability results for feedback set problems in tournaments

Cites Work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• A Min-Max Theorem on Feedback Vertex Sets