On the complexity of finding balanced oneway cuts

DOI10.1016/S0020-0190(03)00251-5zbMath1175.68188MaRDI QIDQ1014383

Orly Yahalom, Uriel Feige

Publication date: 28 April 2009

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

directed graphNP-hardgraph algorithmsbisection

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Solving cut-problems in quadratic time for graphs with bounded treewidth ⋮ Bipartitioning of directed and mixed random graphs ⋮ Most balanced minimum cuts ⋮ Unnamed Item ⋮ A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding good approximate vertex and edge partitions is NP-hard
• Some simplified NP-complete graph problems
• A Polylogarithmic Approximation of the Minimum Bisection
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Depth-First Search and Linear Graph Algorithms
• The NP-completeness column: An ongoing guide

This page was built for publication: On the complexity of finding balanced oneway cuts