Multicut problems in almost-planar graphs: the dependency of complexity on the demand pattern

DOI10.4230/LIPICS.ESA.2025.87MaRDI QIDQ7322496zbMATH OpenFDO

Authors Florian Hoersch, Dániel Marx

Publication date 31 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2025.87

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A short proof of the two-commodity flow theorem
• A tight lower bound for planar multiway cut with fixed number of terminals
• Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
• Computing crossing numbers in quadratic time
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Multi-Commodity Network Flows
• Multicut problems in embedded graphs: the dependency of complexity on the demand pattern
• Multicuts in planar and bounded-genus graphs with bounded number of terminals
• Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
• The Complexity of Multiterminal Cuts

This page was built for publication: Multicut problems in almost-planar graphs: the dependency of complexity on the demand pattern

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