The Complexity of Multiterminal Cuts
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Better hardness results for the minimum spanning tree congestion problem
- Multicut problems in embedded graphs: the dependency of complexity on the demand pattern
- Placing quantified variants of 3-SAT and \textsc{not-all-equal} 3-SAT in the polynomial hierarchy
- Mixed-integer programming for cycle detection in nonreversible Markov processes
- Brief announcement: Bounded-degree cut is fixed-parameter tractable
- Eulerian walks in temporal graphs
- Algorithmic aspects of homophyly of networks
- Hardness of approximation for crossing number
- Minimum violation vertex maps and their applications to cut problems
- A logical approach to multicut problems
- Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity
- Compact samples for data dissemination
- An improved parameterized algorithm for the minimum node multiway cut problem
- Defending planar graphs against star-cutsets
- Partial multicuts in trees
- Towards duality of multicommodity multiroute cuts and flows: multilevel ball-growing
- scientific article; zbMATH DE number 7559431 (Why is no real title available?)
- Exponential-time approximation schemes via compression
- A characterization of minimizable metrics in the multifacility location problem
- An O^(1.84ᵏ) parameterized algorithm for the multiterminal cut problem
- Cut problems in graphs with a budget constraint
- The Monotone Satisfiability Problem with Bounded Variable Appearances
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- scientific article; zbMATH DE number 7561552 (Why is no real title available?)
- A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
- Supermodular functions and the complexity of MAX CSP
- Discriminating code and set cover with k-bend paths
- Target set selection with maximum activation time
- Edge identifying codes
- Fixed-parameter algorithms for DAG partitioning
- Analysis of budget for interdiction on multicommodity network flows
- Solving \((k-1)\)-stable instances of \texttt{k-terminal cut} with isolating cuts
- Optimal allocation in combinatorial auctions with quadratic utility functions
- The convexity of induced paths of order three and applications: complexity aspects
- The critical node detection problem in networks: a survey
- Blocking Small Cuts in a Network, and Related Problems
- Fixed-Parameter Algorithms for Finding Agreement Supertrees
- The complexity and approximability of minimum contamination problems
- Structural parameterization of cluster deletion
- Multiway cut and integer flow problems in trees
- Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
- scientific article; zbMATH DE number 2081002 (Why is no real title available?)
- The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
- A Lagrangian relaxation-based heuristic to solve large extended graph partitioning problems
- Path-disruption games: bribery and a probabilistic model
- Clique Cover and Graph Separation
- On the generalized multiway cut in trees problem
- On generalized greedy splitting algorithms for multiway partition problems
- Discrete and continuous models for partitioning problems
- A tight \(\sqrt{2} \)-approximation for linear 3-cut
- Odd multiway cut in directed acyclic graphs
- Geometric multicut: shortest fences for separating groups of objects in the plane
- Partitioning sparse graphs into an independent set and a graph with bounded size components
- FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
- Parameterized complexity of the \(\mathcal{T}_{h+1} \)-free edge deletion problem
- The partition problem
- Political districting to minimize cut edges
- 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
- Exact algorithms for a discrete metric labeling problem
- Almost tight lower bounds for hard cutting problems in embedded graphs
- Beyond Boolean surjective VCSPs
- Approximation algorithms for requirement cut on graphs
- Computing minimum cuts by randomized search heuristics
- On integer and bilevel formulations for the \(k\)-vertex cut problem
- The multi-multiway cut problem
- The Maximum Integer Multiterminal Flow Problem
- Multiway cuts with a choice of representatives
- A new approach for the multiobjective minimum spanning tree
- A survey of parameterized algorithms and the complexity of edge modification
- An improved approximation algorithm of MULTIWAY CUT.
- Approximating submodular matroid-constrained partitioning
- Cardinality constrained and multicriteria (multi)cut problems
- Simple and improved parameterized algorithms for multiterminal cuts
- An improved approximation algorithm for requirement cut
- Better hardness results for the minimum spanning tree congestion problem
- Global and fixed-terminal cuts in digraphs
- Algorithmic and complexity aspects of problems related to total restrained domination for graphs
- Some formulations for the group Steiner tree problem
- Approximation algorithms for vertex happiness
- Distributional limits of graph cuts on discretized grids
- Approximation algorithms for feasible cut and multicut problems
- Total (restrained) domination in unit disk graphs
- An approximation algorithm for the \(\boldsymbol{K}\)-prize-collecting multicut problem in trees with submodular penalties
- Roman domination in subgraphs of grids
- Approximation Algorithms for CSPs
- Multiterminal flows and cuts
- Performing Multicut on Walkable Environments
- Fast approximate energy minimization with label costs
- Minimum 0-extension problems on directed metrics
- Eisenberg-Gale markets: algorithms and game-theoretic properties
- Reducing the domination number of graphs via edge contractions and vertex deletions
- On embedding complete graphs into hypercubes
- Some constrained partitioning problems and majorization
- Structural parameterization of cluster deletion
- Polyhedral study of the connected subgraph problem
- On quasipolynomial multicut-mimicking networks and kernelization of multiway cut 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)
