A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals

MaRDI QIDQ4607984zbMATH OpenFDO

Authors Vincent Cohen-Addad, Éric Colin de Verdière, Arnaud de Mesmay

Publication date 15 March 2018

Full work available at URL http://dl.acm.org/citation.cfm?id=3175400

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
• A simple algorithm for multicuts in planar graphs with outer terminals
• A polynomial-time approximation scheme for planar multiway cut

Cited in

(4)

• A fixed parameter tractable approximation scheme for the optimal cut graph of a surface
• Almost tight lower bounds for hard cutting problems in embedded graphs
• A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
• Approximating maximum integral multiflows on bounded genus graphs

This page was built for publication: A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals

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