Exact algorithms for the vertex separator problem in graphs

DOI10.1002/net.20420zbMath1219.05192OpenAlexW2139900483MaRDI QIDQ3008917

Victor F. Cavalcante, Cid Carvalho De Souza

Publication date: 22 June 2011

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20420

zbMATH Keywords

integer programmingLagrangian relaxationcutting planesrelax-and-cutvertex separator problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

A quality and distance guided hybrid algorithm for the vertex separator problem ⋮ A hybrid breakout local search and reinforcement learning approach to the vertex separator problem

Cites Work

• Unnamed Item
• Non delayed relax-and-cut algorithms
• An enhanced TSP-based heuristic for makespan minimization in a flow shop with setup times
• Stronger \(K\)-tree relaxations for the vehicle routing problem
• A relax-and-cut algorithm for the set partitioning problem
• The vertex separator problem: algorithms and computations
• The vertex separator problem: a polyhedral investigation
• Lower and upper bounds for the degree-constrained minimum spanning tree problem
• Lagrangian Relaxation and Cutting Planes for the Vertex Separator Problem
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• A restricted Lagrangean approach to the traveling salesman problem
• Decomposing Matrices into Blocks
• Optimal rectangular partitions
• Algorithms – ESA 2005

This page was built for publication: Exact algorithms for the vertex separator problem in graphs