Approximating minimum feedback sets and multi-cuts in directed graphs

DOI10.1007/3-540-59408-6_38zbMath1498.90238OpenAlexW1517065489MaRDI QIDQ5101402

Baruch Schieber, Guy Even, Joseph (Seffi) Naor

Publication date: 30 August 2022

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59408-6_38

zbMATH Keywords

approximation algorithmsdirected cycles\textsc{fes} problemweighted feedback vertex set (\textsc{fvs}) problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

On the feedback number of 3-uniform linear extremal hypergraphs ⋮ Revisiting the minimum breakpoint linearization problem ⋮ A new interpretation and derivation of the Swaps index

Cites Work

• Retiming synchronous circuitry
• Packing directed circuits fractionally
• Reducibility among Combinatorial Problems
• A parallel approximation algorithm for positive linear programming
• Approximate max-flow min-(multi)cut theorems and their applications
• Multi-Commodity Network Flows

This page was built for publication: Approximating minimum feedback sets and multi-cuts in directed graphs