Improved bounds for minimal feedback vertex sets in tournaments

DOI10.1002/jgt.22225zbMath1393.05136OpenAlexW2775048755WikidataQ55008939 ScholiaQ55008939MaRDI QIDQ4581278

Matthias Mnich, Eva-Lotta Teutrine

Publication date: 16 August 2018

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.22225

zbMATH Keywords

tournamentscombinatorial boundsexponential-time algorithmsfeedback vertex sets

Mathematics Subject Classification ID

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
• Unnamed Item
• Sophisticated voting outcomes and agenda control
• On enumerating all minimal solutions of feedback problems
• Fixed-parameter tractability results for feedback set problems in tournaments
• Bounds on the disparity and separation of tournament solutions
• Open problems around exact algorithms
• Banks winners in tournaments are difficult to recognize
• An Approximation Algorithm for 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
• Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds
• Reducibility among Combinatorial Problems
• Exact Algorithms via Monotone Local Search
• On maximal transitive subtournaments

This page was built for publication: Improved bounds for minimal feedback vertex sets in tournaments