On the complexity of finding balanced oneway cuts
type: Item
instance of: scholarly article
title: On the complexity of finding balanced oneway cuts
zbMATH Open document ID: 1175.68188
DOI: 10.1016/S0020-0190(03)00251-5
author: Orly Yahalom
author: Uriel Feige
published in: Information Processing Letters
publication date: 2009-04-28T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5547769
zbMATH Keywords: bisection
zbMATH Keywords: directed graph
zbMATH Keywords: NP-hard
zbMATH Keywords: graph algorithms
MaRDI profile type: Publication
cites work: Finding good approximate vertex and edge partitions is NP-hard
cites work: Q4035360
cites work: A polylogarithmic approximation of the minimum bisection
cites work: Some simplified NP-complete graph problems
cites work: The NP-completeness column: An ongoing guide
cites work: Q4142699
cites work: Q5585020
cites work: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
cites work: Depth-First Search and Linear Graph Algorithms
Recommended article: Q4500843
Recommended article: Approximation algorithms for maximum cut with limited unbalance
Recommended article: Q4448767
Recommended article: Computing and Combinatorics
Recommended article: Q5387696
Recommended article: On the approximability of Max-Cut
Recommended article: On the computational complexity of cut-reduction
Recommended article: Complexity and approximability of the k‐way vertex cut
Recommended article: One-third-integrality in the max-cut problem
Recommended article: On the Complexity of Finding an Unknown Cut Via Vertex Queries
description: scientific article; zbMATH DE number 5547769