A simple algorithm for multicuts in planar graphs with outer terminals

DOI10.1016/J.DAM.2008.11.010MaRDI QIDQ1026166zbMATH OpenOpenAlexFDO

Authors Cédric Bentz

Publication date 24 June 2009

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2008.11.010

zbMATH Keywords

graph algorithmsplanar graphsmulticuts

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs
• An FPT algorithm for planar multicuts with sources and sinks on the outer face
• The planar multiterminal cut problem

Cites work

• scientific article; zbMATH DE number 3876616 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Approximation algorithms for NP-complete problems on planar graphs
• Combinatorial optimization. Theory and algorithms.
• Edge-disjoint paths in planar graphs
• Efficient algorithms for \(k\)-terminal cuts on planar graphs
• Graph minors. VI. Disjoint paths across a disc
• Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
• Maximal Flow Through a Network
• Multicommodity flows in planar graphs
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• Multiway cuts in node weighted graphs
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs
• Primal-dual approximation algorithms for integral flow and multicut in trees
• The Complexity of Multiterminal Cuts
• The planar multiterminal cut problem
• Two-Connected Augmentation Problems in Planar Graphs

Cited in

(8)

• New results on planar and directed multicuts
• Efficient algorithms for \(k\)-terminal cuts on planar graphs
• A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs
• A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
• A polynomial-time approximation scheme for planar multiway cut
• A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
• An FPT algorithm for planar multicuts with sources and sinks on the outer face
• Refined vertex sparsifiers of planar graphs

This page was built for publication: A simple algorithm for multicuts in planar graphs with outer terminals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1026166)