New results on planar and directed multicuts
DOI10.1016/J.ENDM.2009.07.034zbMATH Open1273.05215OpenAlexW2030755499MaRDI QIDQ2851464FDOQ2851464
Authors: Cédric Bentz 
Publication date: 10 October 2013
Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.endm.2009.07.034
Recommendations
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cites Work
- The Complexity of Multiterminal Cuts
- Multiway cuts in node weighted graphs
- Minimal multicut and maximal integer multiflow: a survey
- Title not available (Why is that?)
- On the hardness of approximating Multicut and Sparsest-Cut
- Primal-dual approximation algorithms for integral flow and multicut in trees
- On the complexity of the multicut problem in bounded tree-width graphs and digraphs
- Hardness of cut problems in directed graphs
- Tightening non-simple paths and cycles on surfaces
- Efficient algorithms for \(k\)-terminal cuts on planar graphs
- A simple algorithm for the planar multiway cut problem
- A simple algorithm for multicuts in planar graphs with outer terminals
Cited In (6)
- The complexity of multicut and mixed multicut problems in (di)graphs
- Revisiting a simple algorithm for the planar multiterminal cut problem
- An FPT algorithm for planar multicuts with sources and sinks on the outer face
- On the hardness of finding near-optimal multicuts in directed acyclic graphs
- Multicuts in unweighted digraphs with bounded degree and bounded tree-width
- Global and fixed-terminal cuts in digraphs
This page was built for publication: New results on planar and directed multicuts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2851464)
