Multi-budgeted directed cuts
DOI10.1007/s00453-019-00609-1zbMath1477.68236arXiv1810.06848OpenAlexW2965452024WikidataQ127408777 ScholiaQ127408777MaRDI QIDQ786027
Marcin Pilipczuk, Magnus Wahlström, Dániel Marx, Stefan Kratsch, Shao-hua Li
Publication date: 12 August 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1810.06848
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 (max. 100)
Cites Work
- Unnamed Item
- The multivariate algorithmic revolution and beyond. Essays dedicated to Michael R. Fellows on the occasion of his 60th birthday
- 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
- 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
- Linear Time Parameterized Algorithms for S <scp>ubset</scp> F <scp>eedback</scp> V <scp>ertex</scp> S <scp>et</scp>
- 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
- Multi-Budgeted Directed Cuts
- 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
