Approximating minimum feedback sets and multicuts in directed graphs
From MaRDI portal
Publication:1386376
DOI10.1007/PL00009191zbMath0897.68078OpenAlexW2070745908WikidataQ59650037 ScholiaQ59650037MaRDI QIDQ1386376
Madhu Sudan, Joseph (Seffi) Naor, Guy Even, Baruch Schieber
Publication date: 1998
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/pl00009191
Related Items (60)
Parameterized algorithms for feedback set problems and their duals in tournaments ⋮ Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT ⋮ Unnamed Item ⋮ Complexity of approximating CSP with balance/hard constraints ⋮ Primal-dual approximation algorithms for feedback problems in planar graphs ⋮ \(\ell ^2_2\) spreading metrics for vertex ordering problems ⋮ Improved bounds on the max-flow min-cut ratio for multicommodity flows ⋮ Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Hardness of fully dense problems ⋮ A survey on the linear ordering problem for weighted or unweighted tournaments ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ Aligning and Labeling Genomes under the Duplication-Loss Model ⋮ Towards a polynomial kernel for directed feedback vertex set ⋮ The complexity of speedrunning video games ⋮ Kernels for deletion to classes of acyclic digraphs ⋮ The multi-multiway cut problem ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Tight Localizations of Feedback Sets ⋮ An Exact Method for the Minimum Feedback Arc Set Problem ⋮ Parameterized Complexity and Approximability of the SLCS Problem ⋮ 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 ⋮ Beyond rankings: comparing directed acyclic graphs ⋮ Parameterized complexity and approximability of the longest compatible sequence problem ⋮ Combinatorial methods for invariance and safety of hybrid systems ⋮ The feedback arc set problem with triangle inequality is a vertex cover problem ⋮ Maximal Acyclic Subgraphs and Closest Stable Matrices ⋮ A spin glass approach to the directed feedback vertex set problem ⋮ Voting Procedures, Complexity of ⋮ MINIMUM FEEDBACK ARC SETS IN ROTATOR AND INCOMPLETE ROTATOR GRAPHS ⋮ Multi-Budgeted Directed Cuts ⋮ Tiers for peers: a practical algorithm for discovering hierarchy in weighted networks ⋮ Subset Feedback Vertex Set Is Fixed-Parameter Tractable ⋮ Polynomial kernels for deletion to classes of acyclic digraphs ⋮ Linear programming based approximation algorithms for feedback set problems in bipartite tournaments ⋮ An updated survey on the linear ordering problem for weighted or unweighted tournaments ⋮ Exact localisations of feedback sets ⋮ Parameterizing above or below guaranteed values ⋮ Unnamed Item ⋮ Feedback arc number and feedback vertex number of Cartesian product of directed cycles ⋮ On the complexity of crossings in permutations ⋮ Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs ⋮ Parameterized algorithms for generalizations of directed feedback vertex set ⋮ Iterative Compression for Exactly Solving NP-Hard Minimization Problems ⋮ A unified approximation algorithm for node-deletion problems ⋮ On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems ⋮ An FPT algorithm for edge subset feedback edge set ⋮ Parameterised algorithms for deletion to classes of DAGs ⋮ Design of fixed points in Boolean networks using feedback vertex sets and model reduction ⋮ Models for concurrent product and process design ⋮ Multi-budgeted directed cuts ⋮ Tournaments and Semicomplete Digraphs ⋮ Euler Digraphs ⋮ Locally Semicomplete Digraphs and Generalizations ⋮ Unnamed Item ⋮ An Improved Exact Algorithm for Undirected Feedback Vertex Set ⋮ An improved exact algorithm for undirected feedback vertex set
This page was built for publication: Approximating minimum feedback sets and multicuts in directed graphs
