Most balanced minimum cuts

DOI10.1016/j.dam.2009.09.010zbMath1226.05142OpenAlexW2047642894MaRDI QIDQ968139

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

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

Related Items (2)

Graph Bisection with Pareto Optimization ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Partially ordered knapsack and applications to scheduling
• On the complexity of finding balanced oneway cuts
• Recognition algorithms for orders of small width and graphs of small Dilworth number
• On the hardness of approximating Multicut and Sparsest-Cut
• 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 the Minimum Cut of Planarizations
• On the structure of all minimum cuts in a network and applications
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
• Suboptimal cuts: Their enumeration, weight and number

This page was built for publication: Most balanced minimum cuts