An FPT algorithm for planar multicuts with sources and sinks on the outer face

DOI10.1007/s00453-018-0443-4zbMath1410.68151arXiv1708.05903OpenAlexW2964006350WikidataQ129976784 ScholiaQ129976784MaRDI QIDQ1755788

Cédric Bentz

Publication date: 11 January 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1708.05903

zbMATH Keywords

multicutsplanar graphsFPT algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Cardinality constrained and multicriteria (multi)cut problems
• A simple algorithm for multicuts in planar graphs with outer terminals
• Efficient algorithms for \(k\)-terminal cuts on planar graphs
• Multicuts in planar and bounded-genus graphs with bounded number of terminals
• A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
• Approximating the k-multicut problem
• The Complexity of Multiterminal Cuts
• A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs
• Tightening Nonsimple Paths and Cycles on Surfaces
• Multicut is FPT
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset

This page was built for publication: An FPT algorithm for planar multicuts with sources and sinks on the outer face