Multicut problems in embedded graphs: the dependency of complexity on the demand pattern
From MaRDI portal
Cites work
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- A short proof of the two-commodity flow theorem
- A subexponential parameterized algorithm for subset TSP on planar graphs
- A tight lower bound for planar multiway cut with fixed number of terminals
- Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
- Can you beat treewidth?
- Detecting and counting small patterns in planar graphs in subexponential parameterized time
- Faster maxflow via improved dynamic spectral vertex sparsifiers
- Fine-grained parameterized complexity analysis of graph coloring problems
- List-coloring -- parameterizing from triviality
- Maximal Flow Through a Network
- Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
- Multi-Commodity Network Flows
- Multicuts in planar and bounded-genus graphs with bounded number of terminals
- On structural parameterizations of the selective coloring problem
- On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs
- Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams
- Parameterized algorithms
- Parameterized and Exact Computation
- Parameterized coloring problems on chordal graphs
- Parameterized complexity of vertex colouring
- Parameterized graph separation problems
- Parameterized pre-coloring extension and list coloring problems
- Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering
- Subexponential parameterized odd cycle transversal on planar graphs
- The Complexity of Multiterminal Cuts
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
- Vertex Coloring of Comparability+ke and –ke Graphs
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
This page was built for publication: Multicut problems in embedded 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 Q6895843)
