New results on planar and directed multicuts

DOI10.1016/j.endm.2009.07.034zbMath1273.05215OpenAlexW2030755499MaRDI QIDQ2851464

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

multicutsgraph algorithmsAPX-hardness

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

Revisiting a simple algorithm for the planar multiterminal cut problem

Cites Work

• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Minimal multicut and maximal integer multiflow: a survey
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs
• A simple algorithm for multicuts in planar graphs with outer terminals
• Efficient algorithms for \(k\)-terminal cuts on planar graphs
• On the hardness of approximating Multicut and Sparsest-Cut
• A Simple Algorithm for the Planar Multiway Cut Problem
• Hardness of cut problems in directed graphs
• Tightening non-simple paths and cycles on surfaces
• The Complexity of Multiterminal Cuts
• Multiway cuts in node weighted graphs

This page was built for publication: New results on planar and directed multicuts