New results on planar and directed multicuts

DOI10.1016/J.ENDM.2009.07.034MaRDI QIDQ2851464zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

graph algorithmsAPX-hardnessmulticuts

Mathematics Subject Classification ID

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)

Recommendations

• On the hardness of finding near-optimal multicuts in directed acyclic graphs
• A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs
• SOFSEM 2006: Theory and Practice of Computer Science

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• A simple algorithm for multicuts in planar graphs with outer terminals
• A simple algorithm for the planar multiway cut problem
• Efficient algorithms for \(k\)-terminal cuts on planar graphs
• Hardness of cut problems in directed graphs
• Minimal multicut and maximal integer multiflow: a survey
• Multiway cuts in node weighted graphs
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs
• On the hardness of approximating Multicut and Sparsest-Cut
• Primal-dual approximation algorithms for integral flow and multicut in trees
• The Complexity of Multiterminal Cuts
• Tightening non-simple paths and cycles on surfaces

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)