The Complexity of Multiterminal Cuts
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Color-texture segmentation using unsupervised graph cuts
- Cardinality constrained and multicriteria (multi)cut problems
- A simple algorithm for multicuts in planar graphs with outer terminals
- Min Cut is NP-complete for edge weighted trees
- The planar multiterminal cut problem
- Minimum multiway cuts in trees
- Metrics with finite sets of primitive extensions
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- On weighted multiway cuts in trees
- An improved approximation algorithm of MULTIWAY CUT.
- A characterization of minimizable metrics in the multifacility location problem
- On embedding complete graphs into hypercubes
- A new approach for the multiobjective minimum spanning tree
- The convexity of induced paths of order three and applications: complexity aspects
- Partial inverse maximum spanning tree in which weight can only be decreased under l_p-norm
- The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut
- The critical node detection problem in networks: a survey
- Improved approximation algorithms for the maximum happy vertices and edges problems
- L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
- An FPT algorithm for planar multicuts with sources and sinks on the outer face
- Parameterized complexity of the spanning tree congestion problem
- Greedy splitting algorithms for approximating multiway partition problems
- Parameterized complexity of length-bounded cuts and multicuts
- Evolutionary trees: An integer multicommodity max-flow -- min-cut theorem
- A greedy algorithm for multicut and integral multiflow in rooted trees
- Some constrained partitioning problems and majorization
- On generalized greedy splitting algorithms for multiway partition problems
- Hard cases of the multifacility location problem
- A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms
- Multiterminal flows and cuts
- A golden ratio parameterized algorithm for cluster editing
- Two-stage robust network design with exponential scenarios
- Hardness of approximation for crossing number
- Models and methods for solving the problem of network vulnerability
- Generating partitions of a graph into a fixed number of minimum weight cuts
- Complexity and characterization aspects of edge-related domination for graphs
- Inequity aversion pricing over social networks: approximation algorithms and hardness results
- Minimum 0-extension problems on directed metrics
- Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem
- Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties
- Political districting to minimize cut edges
- Königsberg sightseeing: Eulerian walks in temporal graphs
- A graph theoretical approach to the firebreak locating problem
- Solving \((k-1)\)-stable instances of \texttt{k-terminal cut} with isolating cuts
- On the (near) optimality of extended formulations for multi-way cut in social networks
- _p-norm multiway cut
- Complexity of paired domination in AT-free and planar graphs
- Placing quantified variants of 3-SAT and \textsc{not-all-equal} 3-SAT in the polynomial hierarchy
- Partitioning sparse graphs into an independent set and a graph with bounded size components
- On integer and bilevel formulations for the \(k\)-vertex cut problem
- A tight \(\sqrt{2} \)-approximation for linear 3-cut
- Geometric multicut: shortest fences for separating groups of objects in the plane
- Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
- Reducing the domination number of graphs via edge contractions and vertex deletions
- Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem
- Discrete and continuous models for partitioning problems
- Capacitated partial inverse maximum spanning tree under the weighted Hamming distance
- Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
- A simple algorithm for the multiway cut problem
- Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
- Beating the 2-approximation factor for global bicut
- Approximation algorithms for vertex happiness
- On the parameterized complexity of separating certain sources from the target
- Fixed-parameter tractability for subset feedback set problems with parity constraints
- The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
- Complexity dichotomy for oriented homomorphism of planar graphs with large girth
- On Lipschitz extension from finite subsets
- The partition problem
- A logical approach to multicut problems
- Separation of partition inequalities with terminals
- One more well-solved case of the multifacility location problem
- Supermodular functions and the complexity of MAX CSP
- An improved parameterized algorithm for the minimum node multiway cut problem
- Parameterized algorithms for min-max multiway cut and list digraph homomorphism
- Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability
- The vertex \(k\)-cut problem
- On the generalized multiway cut in trees problem
- An O^(1.84ᵏ) parameterized algorithm for the multiterminal cut problem
- On the complexity of the selective graph coloring problem in some special classes of graphs
- Cut problems in graphs with a budget constraint
- The complexity of soft constraint satisfaction
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- Steiner diagrams and \(k\)-star hubs
- Optimal 3-terminal cuts and linear programming
- Some formulations for the group Steiner tree problem
- Correlation clustering in general weighted graphs
- Generalized \(k\)-multiway cut problems
- On a bidirected relaxation for the MULTIWAY CUT problem
- Parameterized complexity of the anchored k-core problem for directed graphs
- List coloring in the absence of two subgraphs
- On the connectivity preserving minimum cut problem
- The maximum integer multiterminal flow problem in directed graphs
- Extended cuts
- On the minimum and maximum selective graph coloring problems in some graph classes
- Mean isoperimetry with control on outliers: exact and approximation algorithms
- Submodular reassignment problem for reallocating agents to tasks with synergy effects
- Eulerian walks in temporal graphs
- A simple algorithm for the planar multiway cut problem
- A new-old algorithm for minimum-cut and maximum-flow in closure graphs.
- A Lagrangian relaxation-based heuristic to solve large extended graph partitioning problems
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)
