A linear time algorithm for graph partition problems

DOI10.1016/0020-0190(92)90126-GzbMath0765.68045OpenAlexW1991957444MaRDI QIDQ1198016

Farhad Shahrokhi, Lane H. Clark, László A. Székely

Publication date: 16 January 1993

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

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90126-g

zbMATH Keywords

linear time algorithmgraph partitionpartitioning algorithmsmaximum cut problembottleneck bipartite number problemgraph bisection problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (5)

Tree partitioning under constraints. -- Clustering for vehicle routing problems ⋮ A note on edge-based graph partitioning and its linear algebraic structure ⋮ A linear time algorithm for graph partition problems ⋮ Path optimization for graph partitioning problems ⋮ Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparsest cuts and bottlenecks in graphs
• A linear time algorithm for graph partition problems
• Some simplified NP-complete graph problems
• The maximum concurrent flow problem

This page was built for publication: A linear time algorithm for graph partition problems