A multilevel bilinear programming algorithm for the vertex separator problem
From MaRDI portal
(Redirected from Publication:683341)
Abstract: The Vertex Separator Problem for a graph is to find the smallest collection of vertices whose removal breaks the graph into two disconnected subsets that satisfy specified size constraints. In the paper 10.1016/j.ejor.2014.05.042, the Vertex Separator Problem was formulated as a continuous (non-concave/non-convex) bilinear quadratic program. In this paper, we develop a more general continuous bilinear program which incorporates vertex weights, and which applies to the coarse graphs that are generated in a multilevel compression of the original Vertex Separator Problem. A Mountain Climbing Algorithm is used to find a stationary point of the continuous bilinear quadratic program, while second-order optimality conditions and perturbation techniques are used to escape from either a stationary point or a local maximizer. The algorithms for solving the continuous bilinear program are employed during the solution and refinement phases in a multilevel scheme. Computational results and comparisons demonstrate the advantage of the proposed algorithm.
Recommendations
- The vertex separator problem: a polyhedral investigation
- Continuous quadratic programming formulations of optimization problems on graphs
- An exact algorithm for solving the vertex separator problem
- The vertex separator problem: algorithms and computations
- Exact algorithms for the vertex separator problem in graphs
Cites work
- scientific article; zbMATH DE number 3858396 (Why is no real title available?)
- scientific article; zbMATH DE number 3816913 (Why is no real title available?)
- scientific article; zbMATH DE number 741125 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- A cutting plane algorithm for solving bilinear programs
- A parallel graph partitioning algorithm for a message-passing multiprocessor
- A recursive bipartitioning algorithm for permuting sparse square matrices into block diagonal form with overlap
- Advanced coarsening schemes for graph partitioning
- Algebraic distance on graphs
- An Efficient Heuristic Procedure for Partitioning Graphs
- An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
- An efficient hybrid algorithm for the separable convex quadratic knapsack problem
- Breakout local search for the quadratic assignment problem
- Continuous quadratic programming formulations of optimization problems on graphs
- Direct Methods for Sparse Linear Systems
- Finding good approximate vertex and edge partitions is NP-hard
- Geometric Separators for Finite-Element Meshes
- Graph minimum linear arrangement by multilevel weighted edge contractions
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Linear programming. Foundations and extensions
- NP-completeness of the Planar Separator Problems
- Optimality conditions for maximizing a function over a polyhedron
- Partitioning Sparse Matrices with Eigenvectors of Graphs
- Partitioning hypergraphs in scientific computing applications through vertex separators on graphs
- Relaxation-based coarsening and multiscale graph organization
- The MIN-cut and vertex separator problem
- The University of Florida sparse matrix collection
Cited in
(12)- The multi-terminal vertex separator problem: branch-and-cut-and-price
- Continuous quadratic programming formulations of optimization problems on graphs
- A note on the SDP relaxation of the minimum cut problem
- A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem
- Relaxation-based coarsening for multilevel hypergraph partitioning
- Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem
- The MIN-cut and vertex separator problem
- The vertex separator problem: algorithms and computations
- An efficient hybrid algorithm for the separable convex quadratic knapsack problem
- Multilevel graph partitioning for three-dimensional discrete fracture network flow simulations
- Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
- Two new integer linear programming formulations for the vertex bisection problem
This page was built for publication: A multilevel bilinear programming algorithm for the vertex separator problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q683341)
