Exact algorithms for the vertex separator problem in graphs

DOI10.1002/NET.20420MaRDI QIDQ3008917zbMATHOpenAlexFDO

Authors 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 programmingcutting planesLagrangian relaxationrelax-and-cutvertex separator problem

Mathematics Subject Classification ID

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

Recommendations

• An exact algorithm for solving the vertex separator problem
• The vertex separator problem: algorithms and computations
• An exact algorithm for graph partitioning
• The vertex separator problem: a polyhedral investigation
• Exact algorithms for difficult graph problems
• An exact combinatorial algorithm for minimum graph bisection
• scientific article; zbMATH DE number 4062622
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Theoretical Computer Science
• scientific article; zbMATH DE number 1953093

Cites work

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

Cited in

(10)

• scientific article; zbMATH DE number 1953093 (Why is no real title available?)
• An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications
• A hybrid breakout local search and reinforcement learning approach to the vertex separator problem
• Vertex Exponential Algorithms for Connected f-Factors
• A quality and distance guided hybrid algorithm for the vertex separator problem
• Finding minimum balanced separators -- an exact approach
• Lagrangian Relaxation and Cutting Planes for the Vertex Separator Problem
• A multilevel bilinear programming algorithm for the vertex separator problem
• An exact combinatorial algorithm for minimum graph bisection
• The vertex separator problem: algorithms and computations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3008917)