The Complexity of Multiterminal Cuts
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- The complexity of multicut and mixed multicut problems in (di)graphs
- An approximation algorithm for max \(k\)-uncut with capacity constraints
- Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
- A polynomial-time approximation scheme for planar multiway cut
- A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case
- Parameterized complexity of the spanning tree congestion problem
- Parameterized complexity of the anchored k-core problem for directed graphs
- Extended cuts
- On the minimum and maximum selective graph coloring problems in some graph classes
- Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
- Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability
- CPG graphs: some structural and hardness results
- The multi-terminal vertex separator problem: branch-and-cut-and-price
- Experimental evaluation of a local search approximation algorithm for the multiway cut problem
- Greedy splitting algorithms for approximating multiway partition problems
- A new-old algorithm for minimum-cut and maximum-flow in closure graphs.
- Evolutionary trees: An integer multicommodity max-flow -- min-cut theorem
- On the parameterized complexity of separating certain sources from the target
- Correlation clustering in general weighted graphs
- scientific article; zbMATH DE number 7561502 (Why is no real title available?)
- Disjoint paths in sparse graphs
- Optimal cuts in graphs and statistical mechanics
- On Lipschitz extension from finite subsets
- The vertex \(k\)-cut problem
- Discrete convexity and polynomial solvability in minimum 0-extension problems
- scientific article; zbMATH DE number 7559417 (Why is no real title available?)
- Approximating maximum integral multiflows on bounded genus graphs
- A local search approximation algorithm for the multiway cut problem
- Algorithms for Multiterminal Cuts
- The planar multiterminal cut problem
- Improved parameterized and exact algorithms for cut problems on trees
- Minimal multicut and maximal integer multiflow: a survey
- A simple algorithm for the multiway cut problem
- Parameterized complexity of weighted multicut in trees
- Parameterized complexity of multicut in weighted trees
- Parameterized graph separation problems
- Approximation algorithms and hardness of the \(k\)-route cut problem
- On a bidirected relaxation for the MULTIWAY CUT problem
- Minimum multiway cuts in trees
- On computing the maximum parsimony score of a phylogenetic network
- Models and methods for solving the problem of network vulnerability
- A sufficiently fast algorithm for finding close to optimal clique trees
- Inapproximability of the Tutte polynomial
- An approximation algorithm for the generalized k-multicut problem
- On the connectivity preserving minimum cut problem
- Revisiting a simple algorithm for the planar multiterminal cut problem
- A graph theoretical approach to the firebreak locating problem
- Color-texture segmentation using unsupervised graph cuts
- The multi-terminal maximum-flow network-interdiction problem
- Fixed-parameter tractability for subset feedback set problems with parity constraints
- Min Cut is NP-complete for edge weighted trees
- The single allocation problem in the interacting three-hub network
- Partial inverse maximum spanning tree in which weight can only be decreased under \(l_p\)-norm
- Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem
- The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut
- Approximation and kernelization for chordal vertex deletion
- Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
- Hard cases of the multifacility location problem
- On approximating the memory-constrained module allocation problem
- Quick separation in chordal and split graphs
- On the (near) optimality of extended formulations for multi-way cut in social networks
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- On interval representations of graphs
- An FPT algorithm for planar multicuts with sources and sinks on the outer face
- Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree
- Improved approximation algorithms for the maximum happy vertices and edges problems
- L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
- On the hardness of finding near-optimal multicuts in directed acyclic graphs
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- scientific article; zbMATH DE number 176254 (Why is no real title available?)
- Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs
- On weighted multiway cuts in trees
- Improving the integrality gap for multiway cut
- Generalized \(k\)-multiway cut problems
- Steiner diagrams and \(k\)-star hubs
- On the complexity of the multicut problem in bounded tree-width graphs and digraphs
- Simplex partitioning via exponential clocks and the multiway-cut problem
- Restricted vertex multicut on permutation graphs
- Improved approximation algorithms for the maximum happy vertices and edges problems
- Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles
- Fun with replicas: tripartitions in tensor networks and gravity
- A golden ratio parameterized algorithm for cluster editing
- Generating partitions of a graph into a fixed number of minimum weight cuts
- On the complexity of target set selection in simple geometric networks
- Deterministic enumeration of all minimum cut-sets and \(k\)-cut-sets in hypergraphs for fixed \(k\)
- One more well-solved case of the multifacility location problem
- Finding a small number of colourful components
- Multiway cuts in directed and node weighted graphs
- Parameterized complexity of length-bounded cuts and multicuts
- Inequity aversion pricing over social networks: approximation algorithms and hardness results
- Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem
- Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
- A faster parameterized algorithm for Group Feedback Edge Set
- The \textsc{Red-Blue Separation} problem on graphs
- A greedy algorithm for multicut and integral multiflow in rooted trees
- Identifying codes in line graphs
- Algorithms for shortest paths and d-cycle problems
- Establishing herd immunity is hard even in simple geometric networks
- Complexity of metric dimension on planar graphs
- Exact algorithms for a discrete metric labeling problem
This page was built for publication: The Complexity of Multiterminal Cuts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4305362)
