Spectral methods for graph bisection problems.

DOI10.1016/S0305-0548(98)00021-5zbMath1040.90558MaRDI QIDQ1406654

Hsuanjen Cheng, Chih-Chien Tu

Publication date: 7 September 2003

Published in: Computers \& Operations Research (Search for Journal in Brave)

zbMATH Keywords

semidefinite programming; eigenvector; subgradient method; interior point method; Eigenvalue

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C22: Semidefinite programming

90C51: Interior-point methods

90C52: Methods of reduced gradient type

Related Items

Algorithms for graph partitioning problems by means of eigenspace relaxations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A parallel algorithm for bisection width in trees
• Some simplified NP-complete graph problems
• A computational study of graph partitioning
• A projection technique for partitioning the nodes of a graph
• On Minimizing the Maximum Eigenvalue of a Symmetric Matrix
• A New Heuristic for Partitioning the Nodes of a Graph
• Large-Scale Optimization of Eigenvalues
• On Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear Programming
• The Optimal Partitioning of Graphs
• An Efficient Heuristic Procedure for Partitioning Graphs
• An Algorithm for Partitioning the Nodes of a Graph
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• Semidefinite Programming
• An Interior-Point Method for Semidefinite Programming
• Lower Bounds for the Partitioning of Graphs