A Polynomial Algorithm for the k-cut Problem for Fixed k
From MaRDI portal
Publication:4294727
DOI10.1287/moor.19.1.24zbMath0809.90125OpenAlexW2167637346MaRDI QIDQ4294727
Olivier Goldschmidt, Dorit S. Hochbaum
Publication date: 18 May 1994
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.19.1.24
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Paths and cycles (05C38)
Related Items (70)
On generalized greedy splitting algorithms for multiway partition problems ⋮ Approximation and hardness results for the max \(k\)-uncut problem ⋮ Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ An overview of graph covering and partitioning ⋮ Minimum cost subpartitions in graphs ⋮ Efficient algorithms for the problems of enumerating cuts by non-decreasing weights ⋮ An extended edge-representative formulation for the \(K\)-partitioning problem ⋮ Forming \(k\) coalitions and facilitating relationships in social networks ⋮ Minimum Cuts and Sparsification in Hypergraphs ⋮ Extended formulations for the \(A\)-cut problem ⋮ Global and fixed-terminal cuts in digraphs ⋮ An exact model for cell formation in group technology ⋮ Clique Cover and Graph Separation ⋮ The planar multiterminal cut problem ⋮ The vertex \(k\)-cut problem ⋮ 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 ⋮ Algorithms for Multiterminal Cuts ⋮ The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp> ⋮ Minimum \(d\)-blockers and \(d\)-transversals in graphs ⋮ Partitioning subclasses of chordal graphs with few deletions ⋮ Approximation and Hardness Results for the Max k-Uncut Problem ⋮ On integer and bilevel formulations for the \(k\)-vertex cut problem ⋮ Efficient Algorithms for the k Smallest Cuts Enumeration ⋮ Unnamed Item ⋮ Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems ⋮ Shift of pairwise similarities for data clustering ⋮ A polyhedral study of lifted multicuts ⋮ Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs ⋮ Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem ⋮ Generating partitions of a graph into a fixed number of minimum weight cuts ⋮ New algorithms for a simple measure of network partitioning ⋮ Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs ⋮ An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem ⋮ Mixed-case community detection problem in social networks: algorithms and analysis ⋮ Polyhedral study of the connected subgraph problem ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ Hypergraph \(k\)-cut in randomized polynomial time ⋮ LP Relaxation and Tree Packing for Minimum $k$-Cut ⋮ On the \(k\)-cut problem ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ How to Cut a Graph into Many Pieces ⋮ A new?old algorithm for minimum-cut and maximum-flow in closure graphs ⋮ Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs ⋮ The critical node detection problem in networks: a survey ⋮ Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs. ⋮ Optimal cuts in graphs and statistical mechanics ⋮ Greedy splitting algorithms for approximating multiway partition problems ⋮ Unnamed Item ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ Simple and improved parameterized algorithms for multiterminal cuts ⋮ Unnamed Item ⋮ New algorithms for a simple measure of network partitioning ⋮ Computing minimum multiway cuts in hypergraphs ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ A discrete districting plan ⋮ A new and improved algorithm for the 3-cut problem ⋮ Finding minimum 3-way cuts in hypergraphs ⋮ Beating the 2-approximation factor for global bicut ⋮ Unnamed Item ⋮ Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem ⋮ Computation and algorithm for the minimum \(k\)-edge-connectivity of graphs ⋮ Tight lower bounds for certain parameterized NP-hard problems ⋮ Political districting to minimize cut edges ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time ⋮ New approximations and hardness results for submodular partitioning problems
This page was built for publication: A Polynomial Algorithm for the k-cut Problem for Fixed k
