Most balanced minimum cuts
type: Item
instance of: scholarly article
title: Most balanced minimum cuts
zbMATH Open document ID: 1226.05142
author: Paul Bonsma
published in: Discrete Applied Mathematics
publication date: 2010-05-05T00:00:00Z
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5703729
zbMATH Keywords: balanced cut
zbMATH Keywords: uniformly partially ordered Knapsack (UPOK)
zbMATH Keywords: approximation algorithm
MaRDI profile type: Publication
full work available at URL: j.dam.2009.09.010
OpenAlex ID: W2047642894
cites work: On the hardness of approximating Multicut and Sparsest-Cut
cites work: On the Minimum Cut of Planarizations
cites work: Hardness of cut problems in directed graphs
cites work: Q5315023
cites work: Finding small balanced separators
cites work: On the complexity of finding balanced oneway cuts
cites work: Recognition algorithms for orders of small width and graphs of small Dilworth number
cites work: Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
cites work: Q5514188
cites work: Q4198056
cites work: On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
cites work: Q3140397
cites work: Partially ordered knapsack and applications to scheduling
cites work: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
cites work: On the structure of all minimum cuts in a network and applications
cites work: Suboptimal cuts: Their enumeration, weight and number
DOI: 10.1016/J.DAM.2009.09.010
description: scientific article; zbMATH DE number 5703729