Most balanced minimum cuts

DOI10.1016/J.DAM.2009.09.010zbMATH Open1226.05142OpenAlexW2047642894MaRDI QIDQ968139FDOQ968139

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the hardness of approximating Multicut and Sparsest-Cut
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• On the structure of all minimum cuts in a network and applications
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Recognition algorithms for orders of small width and graphs of small Dilworth number
• Hardness of cut problems in directed graphs
• Partially ordered knapsack and applications to scheduling
• Finding small balanced separators
• 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
• On the complexity of finding balanced oneway cuts
• On the Minimum Cut of Planarizations

Cited In (2)

• Graph Bisection with Pareto Optimization
• Title not available (Why is that?)

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)