Approximating minimum feedback sets and multicuts in directed graphs

Recommendations

Approximating minimum feedback sets and multi-cuts in directed graphs (extended summary)
Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
Approximating minimum feedback vertex sets in hypergraphs
Approximation and Online Algorithms
Approximating directed multicuts
Greedy approximation algorithms for directed multicuts
A lower bound on the integrality gap for minimum multicut in directed networks
Iterative algorithms for generating minimal cutsets in directed graphs
On the hardness of finding near-optimal multicuts in directed acyclic graphs
On locating minimum feedback vertex sets

Cited in

(77)

Parameterizing above or below guaranteed values
Combinatorial algorithms for feedback problems in directed graphs
On the complexity of crossings in permutations
Models for concurrent product and process design
A unified approximation algorithm for node-deletion problems
On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
Approximating minimum feedback vertex sets in hypergraphs
Kernels for deletion to classes of acyclic digraphs
Beyond rankings: comparing directed acyclic graphs
Combinatorial methods for invariance and safety of hybrid systems
Tiers for peers: a practical algorithm for discovering hierarchy in weighted networks
Polynomial kernels for deletion to classes of acyclic digraphs
Improved bounds on the max-flow min-cut ratio for multicommodity flows
Feedback arc number and feedback vertex number of Cartesian product of directed cycles
Parameterised algorithms for deletion to classes of DAGs
Design of fixed points in Boolean networks using feedback vertex sets and model reduction
An improved exact algorithm for undirected feedback vertex set
Parameterized algorithms for min-max multiway cut and list digraph homomorphism
Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT
Hardness of fully dense problems
A survey on the linear ordering problem for weighted or unweighted tournaments
Towards a polynomial kernel for directed feedback vertex set
Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs
An Improved Exact Algorithm for Undirected Feedback Vertex Set
Tournaments and Semicomplete Digraphs
Euler digraphs
Locally Semicomplete Digraphs and Generalizations
Complexity of approximating CSP with balance/hard constraints
Designing FPT algorithms for cut problems using randomized contractions
Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
The complexity of speedrunning video games
A spin glass approach to the directed feedback vertex set problem
scientific article; zbMATH DE number 7232797 (Why is no real title available?)
scientific article; zbMATH DE number 3876618 (Why is no real title available?)
Parameterized Complexity and Approximability of the SLCS Problem
Iterative Compression for Exactly Solving NP-Hard Minimization Problems
Iterative algorithms for generating minimal cutsets in directed graphs
scientific article; zbMATH DE number 139781 (Why is no real title available?)
Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
Parameterized complexity and approximability of the longest compatible sequence problem
Constant factor approximation for subset feedback set problems via a new LP relaxation
Bayesian network learning via topological order
Primal-dual approximation algorithms for feedback problems in planar graphs
The feedback arc set problem with triangle inequality is a vertex cover problem
Minimum feedback arc sets in rotator and incomplete rotator graphs
Multi-budgeted directed cuts
Approximating minimum feedback sets and multi-cuts in directed graphs (extended summary)
Tight localizations of feedback sets
An exact method for the minimum feedback arc set problem
Towards a polynomial kernel for directed feedback vertex set
Maximal acyclic subgraphs and closest stable matrices
Voting procedures, complexity of
Aligning and Labeling Genomes under the Duplication-Loss Model
Linear programming based approximation algorithms for feedback set problems in bipartite tournaments
Inapproximability of \(H\)-transversal/packing
Parameterized algorithms for generalizations of directed feedback vertex set
Multi-robot motion planning for unit discs with revolving areas
Extremal results on feedback arc sets in digraphs
A survey of parameterized algorithms and the complexity of edge modification
Tradeoffs in process strategy games with application in the WDM reconfiguration problem
The connection of the acyclic disconnection and feedback arc sets -- on an open problem of Figueroa et al..
Tree drawings with columns
A better LP rounding for feedback arc set on tournaments
A constant factor approximation for directed feedback vertex set in graphs of bounded genus
Competitive query minimization for stable matching with one-sided uncertainty
Data reduction for directed feedback vertex set on graphs without long induced cycles. Three rules to rule them all
The PACE 2022 parameterized algorithms and computational experiments challenge: directed feedback vertex set
Wannabe bounded treewidth graphs admit a polynomial kernel for directed feedback vertex set
Sometimes hoarding is harder than cleaning: NP-hardness of maximum blocked-clause addition
Exact localisations of feedback sets
An FPT algorithm for edge subset feedback edge set
Multi-budgeted directed cuts
Parameterized algorithms for feedback set problems and their duals in tournaments
\(\ell ^2_2\) spreading metrics for vertex ordering problems
The multi-multiway cut problem
An updated survey on the linear ordering problem for weighted or unweighted tournaments

This page was built for publication: Approximating minimum feedback sets and multicuts in directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1386376)