Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
type: Item
instance of: scholarly article
title: Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
zbMATH Open document ID: 1350.68126
author: Alessandro Maddaloni
author: Saket Saurabh
author: Jørgen Bang-Jensen
published in: Algorithmica
publication date: 2016-10-21T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6642151
zbMATH Keywords: parameterized complexity
zbMATH Keywords: kernels
zbMATH Keywords: feedback vertex set
zbMATH Keywords: feedback arc set
zbMATH Keywords: decomposable digraph
zbMATH Keywords: bounded independence number
zbMATH Keywords: locally semicomplete digraph
zbMATH Keywords: quasi-transitive digraph
MaRDI profile type: Publication
full work available at URL: s00453-015-0038-2
OpenAlex ID: W1048071008
cites work: A kernelization algorithm for \(d\)-hitting set
cites work: Aggregating inconsistent information
cites work: Ranking Tournaments
cites work: Fast FAST
cites work: Locally semicomplete digraphs: A generalization of tournaments
cites work: Digraphs
cites work: Quasi‐transitive digraphs
cites work: Arc-disjoint paths in decomposable 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: The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
cites work: Q3549698
cites work: Tournament immersion and cutwidth
cites work: Q3291037
cites work: Fully dynamic recognition algorithm and certificate for directed cographs
cites work: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
cites work: Fixed-parameter tractability results for feedback set problems in tournaments
cites work: Intersection Theorems for Systems of Sets
cites work: Approximating minimum feedback sets and multicuts in directed graphs
cites work: Parametrized complexity theory.
cites work: Jungles, bundles, and fixed-parameter tractability
cites work: Subexponential Parameterized Algorithm for Computing the Cutwidth of a Semi-complete Digraph
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: Q4198056
cites work: Q4851597
cites work: Q4325297
cites work: Fixed-Parameter Complexity of Feedback Vertex Set in Bipartite Tournaments
cites work: On the structure of local tournaments
cites work: Q4262243
cites work: Reducibility among Combinatorial Problems
cites work: Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
cites work: Faster deterministic \textsc{Feedback Vertex Set}
cites work: Kernelization – Preprocessing with a Guarantee
cites work: A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
cites work: Parameterized algorithms for feedback set problems and their duals in tournaments
cites work: A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
cites work: A 4 k 2 kernel for feedback vertex set
cites work: A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments
DOI: 10.1007/S00453-015-0038-2
description: scientific article; zbMATH DE number 6642151