Finding k Cuts within Twice the Optimal
From MaRDI portal
Publication:4326855
DOI10.1137/S0097539792251730zbMath0828.68082OpenAlexW2122466336MaRDI QIDQ4326855
Vijay V. Vazirani, Huzur Saran
Publication date: 27 March 1995
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539792251730
Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)
Related Items (54)
On the (near) optimality of extended formulations for multi-way cut in social networks ⋮ 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 ⋮ Minimum cost subpartitions in graphs ⋮ Approximation algorithms for requirement cut on graphs ⋮ A derandomized approximation algorithm for the critical node detection problem ⋮ A randomized algorithm with local search for containment of pandemic disease spread ⋮ Minimum Cuts and Sparsification in Hypergraphs ⋮ Critical node detection problem for complex network in undirected weighted networks ⋮ An exact model for cell formation in group technology ⋮ The bi-objective critical node detection problem ⋮ Approximation algorithms for Min-k-overlap problems using the principal lattice of partitions approach ⋮ An approximation algorithm for maxk-uncut with capacity constraints ⋮ Partitioning subclasses of chordal graphs with few deletions ⋮ 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 ⋮ Approximation and hardness results for label cut and related problems ⋮ Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem ⋮ Models and methods for solving the problem of network vulnerability ⋮ Generating partitions of a graph into a fixed number of minimum weight cuts ⋮ New algorithms for a simple measure of network partitioning ⋮ Algorithms for placing monitors in a flow network ⋮ Dynamic Balanced Graph Partitioning ⋮ Cardinality constrained minimum cut problems: complexity and algorithms. ⋮ On the advantage of overlapping clusters for minimizing conductance ⋮ On the sum-max graph partitioning problem ⋮ Hypergraph \(k\)-cut in randomized polynomial time ⋮ Cut problems in graphs with a budget constraint ⋮ LP Relaxation and Tree Packing for Minimum $k$-Cut ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ Approximating \(k\)-cuts using network strength as a Lagrangean relaxation ⋮ Algorithmic aspects of homophyly of networks ⋮ How to Cut a Graph into Many Pieces ⋮ Speeding up the Gomory-Hu parallel cut tree algorithm with efficient graph contractions ⋮ Approximating Requirement Cut via a Configuration LP ⋮ Greedy splitting algorithms for approximating multiway partition problems ⋮ Unnamed Item ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ An improved approximation algorithm for requirement cut ⋮ New algorithms for a simple measure of network partitioning ⋮ 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 ⋮ Unnamed Item ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Symmetric submodular system: contractions and Gomory-Hu tree ⋮ Algorithms for Placing Monitors in a Flow Network ⋮ Beating the 2-approximation factor for global bicut ⋮ Unnamed Item ⋮ Generating irregular partitionable data structures ⋮ 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: Finding k Cuts within Twice the Optimal
