On the hardness of finding near-optimal multicuts in directed acyclic graphs
From MaRDI portal
Publication:719273
DOI10.1016/j.tcs.2011.06.003zbMath1222.68086OpenAlexW2024751798MaRDI QIDQ719273
Publication date: 10 October 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.06.003
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Directed graphs (digraphs), tournaments (05C20)
Related Items (1)
Cites Work
- The dag-width of directed graphs
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Minimal multicut and maximal integer multiflow: a survey
- On the Max-flow min-cut ratio for directed multicommodity flows
- Digraph measures: Kelly decompositions, games, and orderings
- On the complexity of the multicut problem in bounded tree-width graphs and digraphs
- Optimization, approximation, and complexity classes
- A two-commodity cut theorem
- Some APX-completeness results for cubic graphs
- Directed tree-width
- A logical approach to multicut problems
- On the hardness of approximating Multicut and Sparsest-Cut
- The maximum integer multiterminal flow problem in directed graphs
- Hardness of cut problems in directed graphs
- On the Complexity of Timetable and Multicommodity Flow Problems
- Two-Commodity Flow
- The Complexity of Multiterminal Cuts
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- Multiway cuts in node weighted graphs
- Multi-Commodity Network Flows
- Unnamed Item
- Unnamed Item
This page was built for publication: On the hardness of finding near-optimal multicuts in directed acyclic graphs
