A Polynomial Algorithm for the k-cut Problem for Fixed k
From MaRDI portal
Recommendations
Cited in
(97)- The planar multiterminal cut problem
- A new and improved algorithm for the 3-cut problem
- An \(O(k^ 2 n^ 2)\) algorithm to find a \(k\)-partition in a \(k\)- connected graph
- On the k-cut subgraph polytope
- Approximation and hardness results for the max \(k\)-uncut problem
- Forming \(k\) coalitions and facilitating relationships in social networks
- The critical node detection problem in networks: a survey
- Greedy splitting algorithms for approximating multiway partition problems
- Computing minimum multiway cuts in hypergraphs
- On cutting a few vertices from a graph
- On generalized greedy splitting algorithms for multiway partition problems
- Extended formulations for the \(A\)-cut problem
- Generating partitions of a graph into a fixed number of minimum weight cuts
- On the \(k\)-cut problem
- Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem
- Computation and algorithm for the minimum \(k\)-edge-connectivity of graphs
- Political districting to minimize cut edges
- New approximations and hardness results for submodular partitioning problems
- An overview of graph covering and partitioning
- On integer and bilevel formulations for the \(k\)-vertex cut problem
- Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
- Mixed-case community detection problem in social networks: algorithms and analysis
- Hypergraph \(k\)-cut in randomized polynomial time
- A discrete districting plan
- Beating the 2-approximation factor for global bicut
- The vertex \(k\)-cut problem
- Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
- An O^(1.84ᵏ) parameterized algorithm for the multiterminal cut problem
- Tight lower bounds for certain parameterized NP-hard problems
- Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
- A polyhedral study of lifted multicuts
- Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs
- New algorithms for a simple measure of network partitioning
- A new-old algorithm for minimum-cut and maximum-flow in closure graphs.
- The cutting plane method is polynomial for perfect matchings
- The minimum cut cover problem
- Cutting up is hard to do: the parameterised complexity of k-cut and related problems
- Clique Cover and Graph Separation
- Approximation and hardness results for the max \(k\)-uncut problem
- How to Cut a Graph into Many Pieces
- An extended edge-representative formulation for the \(K\)-partitioning problem
- LP relaxation and tree packing for minimum k-cut
- Solving minimum K-cardinality cut problems in planar graphs
- Algorithms for Multiterminal Cuts
- Efficient Algorithms for the k Smallest Cuts Enumeration
- An exact model for cell formation in group technology
- Minimum \(d\)-blockers and \(d\)-transversals in graphs
- Blocking Small Cuts in a Network, and Related Problems
- scientific article; zbMATH DE number 409492 (Why is no real title available?)
- Finding k Cuts within Twice the Optimal
- Minimum cuts and sparsification in hypergraphs
- An FPT algorithm beating 2-approximation for \(k\)-cut
- Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
- Polyhedral study of the connected subgraph problem
- Asymptotically Optimal Linear Algorithm for the Minimum k-Cut in a Random Graph
- scientific article; zbMATH DE number 2119718 (Why is no real title available?)
- A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs
- Global and fixed-terminal cuts in digraphs
- Brief announcement: Bounded-degree cut is fixed-parameter tractable
- Fast and deterministic approximations for \(k\)-cut
- Beyond Boolean surjective VCSPs
- Minimum violation vertex maps and their applications to cut problems
- On the hardness of approximating the \(k\)-\textsc{Way Hypergraph Cut} problem
- A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
- Polynomial-time approximation scheme for minimum \(k\)-cut in planar and minor-free graphs
- The Steiner k-Cut Problem
- Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
- Fast and Deterministic Approximations for k-Cut.
- Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph
- Fixed parameter approximation scheme for min-max \(k\)-cut
- Approximating max k-uncut via LP-rounding plus greed, with applications to densest k-subgraph
- Fixed parameter approximation scheme for min-max \(k\)-cut
- Partitioning subclasses of chordal graphs with few deletions
- Link fault tolerance of BC networks and folded hypercubes on h-extra r-component edge-connectivity
- Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions
- Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs.
- The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>
- New algorithms for a simple measure of network partitioning
- Partitioning subclasses of chordal graphs with few deletions
- Shift of pairwise similarities for data clustering
- Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem
- Mixed-integer linear programming formulations and column generation algorithms for the minimum normalized cuts problem on networks
- Composing dynamic programming tree-decomposition-based algorithms
- Deterministic enumeration of all minimum cut-sets and k-cut-sets in hypergraphs for fixed k
- A polynomial time algorithm for finding a minimum 4-partition of a submodular function
- Approximating submodular \(k\)-partition via principal partition sequence
- A parameterized approximation scheme for min \(k\)-cut
- Distributional limits of graph cuts on discretized grids
- Formulations and branch-and-cut algorithms for cycle covers with up to p cycles
- Exponential-time approximation schemes via compression
- The k-way vertex cut problem on bipartite graphs: complexity results and algorithms
- Minimal multicut and maximal integer multiflow: a survey
- Finding minimum 3-way cuts in hypergraphs
- Minimum cost subpartitions in graphs
- Efficient algorithms for the problems of enumerating cuts by non-decreasing weights
- Optimal cuts in graphs and statistical mechanics
- Simple and improved parameterized algorithms for multiterminal cuts
This page was built for publication: A Polynomial Algorithm for the k-cut Problem for Fixed k
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4294727)
