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