A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
type: Item
instance of: scholarly article
title: A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
zbMATH Open document ID: 1277.05077
author: Pranabendu Misra
author: Venkatesh Raman
author: Saket Saurabh
author: M. S. Ramanujan
published in: Theory of Computing Systems
publication date: 2013-12-02T00:00:00Z
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 6235176
zbMATH Keywords: kernelization
zbMATH Keywords: feedback arc set
zbMATH Keywords: bipartite tournament
MaRDI profile type: Publication
full work available at URL: s00224-013-9453-4
OpenAlex ID: W1990046850
cites work: A kernelization algorithm for \(d\)-hitting set
cites work: Aggregating inconsistent information
cites work: Ranking Tournaments
cites work: Fast FAST
cites work: Digraphs
cites work: A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
cites work: Kernels for feedback arc set in tournaments
cites work: On problems without polynomial kernels
cites work: (Meta) Kernelization
cites work: A Min-Max Theorem on Feedback Vertex Sets
cites work: The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
cites work: Q4243442
cites work: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
cites work: Fixed-parameter tractability results for feedback set problems in tournaments
cites work: Incompressibility through Colors and IDs
cites work: Bidimensionality and Geometric Graphs
cites work: A more effective linear kernelization for cluster editing
cites work: Feedback arc set in bipartite tournaments is NP-complete
cites work: Feedback arc set problem in bipartite tournaments
cites work: A survey of the algorithmic aspects of modular decomposition
cites work: Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
cites work: Q5671815
cites work: Q3549601
cites work: A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments
cites work: Parameterized algorithms for feedback set problems and their duals in tournaments
cites work: Q4694754
cites work: Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
cites work: A 4 k 2 kernel for feedback vertex set
cites work: A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments
cites work: Linear programming based approximation algorithms for feedback set problems in bipartite tournaments
cites work: Q2934620
DOI: 10.1007/S00224-013-9453-4
description: scientific article; zbMATH DE number 6235176