A quadratic vertex kernel for feedback arc set in bipartite tournaments

DOI10.1007/s00453-013-9783-2zbMath1307.05214OpenAlexW2013135423MaRDI QIDQ2258074

Jiong Guo, Mingyu Xiao

Publication date: 2 March 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-013-9783-2

zbMATH Keywords

graph algorithmsbipartite tournamentparameterized algorithmskernelizationfeedback arc set

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

Feedback arc number and feedback vertex number of Cartesian product of directed cycles

Cites Work

• Unnamed Item
• Kernels for feedback arc set in tournaments
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Feedback arc set in bipartite tournaments is NP-complete
• A kernelization algorithm for \(d\)-hitting set
• Fixed-parameter tractability results for feedback set problems in tournaments
• Improved FPT algorithm for feedback vertex set problem in bipartite tournament
• Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
• Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem
• A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments
• Fixed-Parameter Complexity of Feedback Vertex Set in Bipartite Tournaments
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Fast FAST
• Ranking Tournaments
• A Min-Max Theorem on Feedback Vertex Sets

This page was built for publication: A quadratic vertex kernel for feedback arc set in bipartite tournaments