On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments
From MaRDI portal
Publication:2345613
DOI10.1016/j.dam.2015.01.032zbMath1311.05076MaRDI QIDQ2345613
Publication date: 22 May 2015
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2015.01.032
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On making directed graphs transitive
- Kernels for feedback arc set in tournaments
- A kernelization algorithm for \(d\)-hitting set
- On problems without polynomial kernels
- A general method to speed up fixed-parameter-tractable algorithms
- Two edge modification problems without polynomial kernels
- Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
- Hardness of fully dense problems
- A 4 k 2 kernel for feedback vertex set
- 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
- Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
- Fast FAST
- Kernelization: New Upper and Lower Bound Techniques
- Kernelization Lower Bounds by Cross-Composition
- Ranking Tournaments
- Ordering by weighted number of wins gives a good ranking for weighted tournaments