Multi-Budgeted Directed Cuts
DOI10.4230/LIPIcs.IPEC.2018.18zbMath1477.68237OpenAlexW2896371654MaRDI QIDQ5009480
Marcin Pilipczuk, Dániel Marx, Magnus Wahlström, Stefan Kratsch, Shao-hua Li
Publication date: 4 August 2021
Full work available at URL: https://doi.org/10.4230/LIPIcs.IPEC.2018.18
minimum cutfixed-parameter tractabilitydirected feedback vertex setimportant separatorsmulti-budgeted cuts
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Flows in graphs (05C21) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (1)
Cites Work
- Unnamed Item
- FPT algorithms for path-transversal and cycle-transversal problems
- List H-coloring a graph by removing few vertices
- Parameterized graph separation problems
- Almost 2-SAT is fixed-parameter tractable
- Approximating minimum feedback sets and multicuts in directed graphs
- Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
- Half-integrality, LP-branching, and FPT Algorithms
- Rounding algorithms for a geometric embedding of minimum multiway cut
- Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
- On Multiway Cut Parameterized above Lower Bounds
- What’s Next? Future Directions in Parameterized Complexity
- Finding small separators in linear time via treewidth reduction
- Designing FPT Algorithms for Cut Problems Using Randomized Contractions
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Improved approximation for directed cut problems
- Directed multicut is W[1-hard, even for four terminal pairs]
- Multiway cuts in node weighted graphs
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Compression via Matroids
- Representative Sets and Irrelevant Vertices
- Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
- The Steiner k-Cut Problem
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- Parameterized Algorithms
This page was built for publication: Multi-Budgeted Directed Cuts
