A new approximation algorithm for the unbalanced min \(s\)-\(t\) cut problem

DOI10.1016/j.tcs.2015.02.040zbMath1333.05250OpenAlexW1976598820MaRDI QIDQ896163

Peng Zhang

Publication date: 11 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.02.040

zbMATH Keywords

linear programmingapproximation algorithmnetwork communityunbalanced cutMin \(s\)-\(t\) Cut

Mathematics Subject Classification ID

Linear programming (90C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

On the minimum \(s-t\) cut problem with budget constraints ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On cutting a few vertices from a graph
• Multicriteria global minimum cuts
• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• A New Approximation Algorithm for the Unbalanced Min s-t Cut Problem
• Unbalanced Graph Partitioning
• A new approach to the maximum-flow problem
• Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases
• Critical Load Factors in Two-Processor Distributed Systems
• A new approach to the minimum cut problem
• Computing All Small Cuts in an Undirected Network
• A Fast Parametric Maximum Flow Algorithm and Applications
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Algorithms – ESA 2005

This page was built for publication: A new approximation algorithm for the unbalanced min \(s\)-\(t\) cut problem