Most balanced minimum cuts

DOI10.1016/J.DAM.2009.09.010MaRDI QIDQ968139zbMATH OpenOpenAlexFDO

Authors Paul Bonsma

Publication date 5 May 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2009.09.010

zbMATH Keywords

approximation algorithmbalanced cutuniformly partially ordered Knapsack (UPOK)

Mathematics Subject Classification ID

Approximation algorithms (68W25) Paths and cycles (05C38)

Recommendations

• Unbalanced graph cuts with minimum capacity
• Unbalanced graph partitioning
• Balanced partitions of trees and applications
• scientific article; zbMATH DE number 3891429
• Approximating the Maximally Balanced Connected Partition Problem in graphs

Cites work

• scientific article; zbMATH DE number 437525 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
• Finding small balanced separators
• Hardness of cut problems in directed graphs
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• On the Minimum Cut of Planarizations
• On the complexity of finding balanced oneway cuts
• On the hardness of approximating Multicut and Sparsest-Cut
• On the structure of all minimum cuts in a network and applications
• Partially ordered knapsack and applications to scheduling
• Recognition algorithms for orders of small width and graphs of small Dilworth number
• Suboptimal cuts: their enumeration, weight and number (extended abstract)

Cited in

(3)

• Graph bisection with Pareto-optimization
• scientific article; zbMATH DE number 7651198 (Why is no real title available?)
• Graph bisection with Pareto optimization

This page was built for publication: Most balanced minimum cuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q968139)